C&SA | Contents

Volume 60 >>> № 3 MAY — JUNE 2024

-->

UDC 519.7

A.V. Anisimov¹

¹ Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

a.v.anisimov@knu.ua

DIGITAL AUTHENTICATION “FRIEND-OR-FOE”

Abstract. Based on a modified one-time Winternitz signature scheme, we develop a multi-time two-round group authentication protocol of the type “friend-or-foe.” The main construction is as follows. At each authentication session, members of a group sign only designated w-blocks of a random message. The verifier checks the validity of the whole Winternitz signature. Session public keys are created and sent to the verifier at the previous session. This way, they form a hash-connected blockchain. Security of the Winternitz signature and blockchain structure of public keys imply the security of the suggested protocol. A trusted third party is needed for establishing first “genesis” keys. Also, the protocol has the property “honest verifier zero knowledge”.

Keywords: authentication, coalition group, digital signature, the Winternitz signature, blockchain.

full text

REFERENCES

Needham R., Schroeder M. Using encryption for authentication in large networks of computers. Commun. ACM. 1978. Vol. 21, Iss. 12. P. 993–999. https://doi.org/10.1109/TIT.1976.1055638.

Menezes A., Qu M., Vanstone S. Key agreement and the need for authentication. Presentation at PKS ‘95. 1995. Toronto, Canada.

Law L., Menezes A., Qu M., Solinas J., Vanstone S. An efficient protocol for authenticated key agreement. Designs, Codes and Cryptography. 2003. Vol. 28, N 2. P. 119–134. https://doi.org/10.1023/A:1022595222606.

Kaliski B. An unknown key-share attack on the MQV key agreement protocol. ACM Transactions on Information and System Security. 2001. Vol. 4, N 3. P. 275–288. https://doi.org/10.1145/501978.501981.

Menezes A., Ustaoglu B. On the importance of public-key validation in the MQV and HMQV key agreement protocols. Proc. 7th International Conference on Cryptology “Progress In Cryptology — INDOCRYPT 2006” (11-13 December 2006, Kolkata, India). Kolkata, 2006. LNCS. 2006. Vol. 4329. P. 133–147. https://doi.org/10.1007/11535218_33.

Menezes A. Another look at HMQV. Journal of Mathematical Cryptology. 2007. Vol. 1, №. 1. P. 47–64. https://doi.org/10.1515/JMC.2007.004.

Hao F. On robust key agreement based on public key authentication. Proc. 14th International Conference on Financial Cryptography and Data Security (25-28 January 2010, Tenerife, Spain). Tenerife, 2010. LNCS. 2010. Vol. 6052. P. 383–390. https://doi.org/10.1007/ 978-3-642-14577-3_33.

Fiat A., Shamir A. How to prove yourself: practical solutions to identification and signature problems. Proc. Conference in the Theory and Application of Cryptographic Techniques ”Advances in Cryptology — CRYPTO 1986” (11–15 August 1986, Santa Barbara, USA). Santa Barbara, 1986. LNCS. 1987. Vol. 263. P.186–194. https://doi.org/10.1007/3-540-47721-7_12.

Fiege U., Fiat A., Shamir A. Zero knowledge proofs of identity. Proc. 19th Annual ACM Symposium on Theory of Computing (STOC ‘87) (25–27 May 1987, New York, USA). New York, 1987. P. 210–217. .

Guillou L., Quisquater P. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. Proc. Workshop on the Theory and Application of of Cryptographic Techniques “Advances in Cryptology (EUROCRYPT ‘88)” (25–27 May 1988, Davos, Switzerland). Davos, 1988. LNCS. 1988. Vol. 330. P. 123–128. https://doi.org/ 10.1007/3-540-45961-8_11.

Schnorr С.P. Efficient signature generation by smart cards. Journal of Cryptology. 1991. Vol. 4, № 3. P. 161–174. https://doi.org/10.1007/BF00196725.

Shor P.W. Algorithms for quantum computation: Discrete logarithms and factoring. Proc. 35th Annual Symposium on Foundations of Computer Science (20-22 November 1994, Santa Fe, NM, USA). Santa Fe, 1994. P. 124–134. https://doi.org/10.1109/sfcs.1994.365700.

Katz J., Lindell Y. Introduction to Modern Cryptography. Second Edition. New York: Chapman and Hall/CRC, 2015. 603 p. https://doi.org/10.1201/b17668.

Merkle R.C. A certified digital signature. Proc. Conference on the Theory and Application of Cryptology “Advances in Cryptology — CRYPTO’89” (20-24 August 1989, Santa Barbara, CA, USA). Santa Barbara, 1989. LNCS. 1990. Vol. 435. P. 218–238. https://doi.org/10.1007/ 0-387-34805-0_21.

Lamport L. Constructing Digital Signatures from a One Way Function. Technical Report. Computer Science Laboratory, SRI International, 1979. SRI-CSL-98. 8 p. URL: https://lamport.azurewebsites.net/pubs/dig-sig.pdf .

Merkle R.C. Secrecy, Authentication and Public Key Systems: Ph.D. Thesis. Stanford: Stanford University, 1979. 187 p. URL: https://www.ralphmerkle.com/papers/Thesis1979.pdf .

Hevia A., Micciancio D. The provable security of graph-based one-time signatures and extensions to algebraic signatures chemes. Proc. 8th International Conference on the Theory and Application of Cryptology and Information Security “Advances in Cryptology — ASIACRYPT 2002” (1–5 December 2002, Queenstown, New Zealand). Queenstown, 2002. LNCS. 2002. Vol. 2501. P. 379–396. https://doi.org/10.1007/3-540-36178-2_24.

Dods C. Smart N., Stam M. Hash based digital signatures chemes. Proc. 10th IMA International Conference “Cryptography and Coding” (19-21 December 2005, Cirencester, UK). Cirencester, 2005. LNCS. 2005. Vol. 3796. P. 96–115. https://doi.org/10.1007/11586821_8.

Buchmann J., Dahmen E., Ereth S., Hulsing A., Ruckert M. On the security of the Winternitz one-time signature scheme. Proc. 4th International Conference on Cryptology “Progress in Cryptology — Africacrypt 2011” (5–7 July 2011, Dakar, Senegal). Dakar, 2011. LNCS. 2011. Vol. 6737. P. 363–378. https://doi.org/10.1007/978-3-642-21969-6_23.

Hulsing A. W-OTS+ shorter signatures for hash-based signature schemes. Proc. 6th International Conference on Cryptology “Progress in Cryptology — AFRICACRYPT 2013” (22–-24 June 2013, Cairo, Egypt). Cairo, 2013. LNCS. 2013. Vol. 7918. P. 173–188. https://doi.org/10.1007/978-3-642-38553-7_10.