Comparative analysis of one-time hash-based signatures

Authors

DOI:

https://doi.org/10.30837/rt.2020.4.203.01

Keywords:

one-time signatures, Lamport signature, Winternitz signature, post-quantum cryptography

Abstract

Hash-based signatures are a wide class of post-quantum cryptographic algorithms, their security is based on the complexity of collision and preimage search problems for cryptographic hash functions. The main advantages of this class are post-quantization, easy modification and a well-researched mathematical base. The disadvantages are large sizes of signatures and limited number of uses of one key pair. The most promising algorithms of this class include algorithms of the SPHINCS type, which have a complex structure, including, among others, a one-time Winternitz signature. The paper analyzes the existing one-time signature algorithms, both well-known Lamport and Winternitz schemes, taking into account modifications of the latter one, and alternative methods. An analysis of the security of modified algorithms has been shown, which showed that their security is based on the same mathematical basis as the security of the original algorithms. The one-time use requirement remains critical to the safety of each of the algorithms studied. The sizes of keys and signatures and computational complexity of various algorithms are compared, in what their basic differences consist. The modified algorithms do not add fundamentally new components in cryptosystems but they make it possible to achieve a certain optimization, shifting the conditions of space-time compromise. The extended Lamport signature is of a particular interest, having the same computational complexity and key sizes as the original algorithm, and at the same time allowing one to halve the signature size. In the context of the SPHINCS cryptosystem, the Winternitz signature remains the best option, since it allows the complete computation of the public key directly from the signature.

References

[Електронний ресурс] https://csrc.nist.gov/projects/post-quantum-cryptography.

Jean-Phillippe Aumasson and Guillaume Endignoux.: Gravity- SPHINCS – Submission to the NIST’s post-quantum cryptography standardization process. (2017).

Daniel J. Bernstein et al.: SPHINCS+ – Submission to the NIST’s post-quantum cryptography standardization process. (2019).

[Електронний ресурс] https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions.

Daniel J. Bernstein et al. Sphincs: practical stateless hash-based signatures. Cryptology ePrint Archive, Report 2014/795, 2014.

Leslie Lamport. Constructing digital signatures from a one-way func- tion. Technical. Report SRI-CSL-98, SRI International Computer Science Laboratory, 1979.

Ralph C. Merkle. A certified digital signature. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 218–238. Springer, 1989.

Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hulsing, and Markus Ruckert. On the security of the Winternitz one-time signature scheme. In A. Nitaj and D. Pointcheval, editors, Africacrypt 2011, volume 6737 of Lecture Notes in Computer Science, pages 363–378. Springer Berlin / Heidelberg, 2011.

Andreas Huülsing. W-OTS+ – shorter signatures for hash-based signa- ture schemes. In Amr Youssef, Abderrahmane Nitaj, and Aboul-Ella Hassanien, editors, Progress in Cryptology // AFRICACRYPT 2013, volume 7918 of LNCS, pages 173–188. Springer, 2013.

Leonid Reyzin and Natan Reyzin. Better than biba: Short one-time signatures with fast signing and verifying. In Lynn Batten and Jennifer Seberry, editors, Information Security and Privacy, volume 2384 of Lecture Notes in Computer Science, pages 1–47. Springer Berlin / Heidelberg, 2002.

Andreas Huülsing, Lea Rausch, and Johannes Buchmann. Optimal parameters for XMSSMT. In Alfredo Cuzzocrea, Christian Kittl, Dimitris E. Simos, Edgar Weippl, and Lida Xu, editors, Security Engineering and Intelligence Informatics, volume 8128 of Lecture Notes in Computer Science, pages 194–208. Springer Berlin Heidelberg, 2013.

Ю.І. Горбенко, Т.В. Мельник, І.Д. Горбенко. Аналіз потенційних постквантових механізмів електронних підписів на основі геш-функцій // Радиотехника. 2017. Вып. 189.

M.A. Kudinov, E.O. Kiktenko, A.K. Fedorov. Security analysis of the W-OTS+ signature scheme: Updating security bounds – 2020.

Published

2020-12-23

How to Cite

Semenets, V., Marukhnenko, O., Gorbenko, I., & Khalimov, G. (2020). Comparative analysis of one-time hash-based signatures. Radiotekhnika, 4(203), 5–18. https://doi.org/10.30837/rt.2020.4.203.01

Issue

Section

Articles