Authors: Maksim Iavich, Tamari Kuchukhidze, Avtandil Gagnidze
Affiliation: Caucasus University, East West University


Keywords: quantum cryptography; vector commitments; lattice-based vector commitments; Verkle tree; cryptographical application
ABSTRACT. Research on quantum computers has advanced significantly in recent years. If humanity ever creates an effective quantum computer, many of the present public key cryptosystems can be compromised. These cryptosystems are currently found in many commercial products. We have devised solutions that seem to protect us from quantum attacks, but they are unsafe and inefficient for use in everyday life. In the paper, hash-based digital signature techniques are analyzed. Merkle tree based digital signature is assessed. Using a Verkle tree and vector commitments, the paper explores the novel ideas. The authors of this article present a unique technology for developing a post-quantum digital signature system using state-of-the-art Verkle tree technology. Verkle tree, vector commitments, and vector commitments based on lattices for post-quantum features are used for this purpose. The concepts of post-quantum signature design utilizing Verkle Tree are also provided in the paper.


1. Chen, Lily, et al. Report on post-quantum cryptography. Vol. 12. Gaithersburg, MD, USA: US Department of Commerce, National Institute of Standards and Technology, 2016.
2. Buchmann, J., Dahmen, E., Szydlo, M. (2009). Hash-based Digital Signature Schemes. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg.
3. Biswas, Bhaskar, and Nicolas Sendrier. "McEliece cryptosystem implementation: Theory and practice." Post-Quantum Cryptography: Second International Workshop, PQCrypto 2008 Cincinnati, OH, USA, October 17-19, 2008 Proceedings 2. Springer Berlin Heidelberg, 2008.
4. Yin, X.; He, J.; Guo, Y.; Han, D.; Li, K.-C.; Castiglione, A. An Efficient Two-Factor Authentication Scheme Based on the Merkle Tree. Sensors 2020, 20, 5735.
5. Chen, Y.-C.; Chou, Y.-P.; Chou, Y.-C. An Image Authentication Scheme Using Merkle Tree Mechanisms. Future Internet 2019, 11, 149.
6. Lamport, Leslie. "Constructing digital signatures from a one way function.",1979.
7. Post-Quantum Digital Signatures with Attenuated Pulse Generator; M. Iavich, R. Bocu, A. Arakelian, G. Iashvili;, Vol-2698, 2020.
8. Koo, D.; Shin, Y.; Yun, J.; Hur, J. Improving Security and Reliability in Merkle Tree-Based Online Data Authentication with Leakage Resilience. Appl. Sci. 2018, 8, 2532.
9. Sim, M.; Eum, S.; Song, G.; Yang, Y.; Kim, W.; Seo, H. K-XMSS and K-SPHINCS+: Enhancing Security in Next-Generation Mobile Communication and Internet Systems with Hash Based Signatures Using Korean Cryptography Algorithms. Sensors 2023, 23, 7558.
10. Merkle, R.C. (1988). A Digital Signature Based on a Conventional Encryption Function. In: Pomerance, C. (eds) Advances in Cryptology — CRYPTO ’87. CRYPTO 1987. Lecture Notes in Computer Science, vol 293. Springer, Berlin, Heidelberg.
11. Chen, H.; Liang, D. Adaptive Spatio-Temporal Query Strategies in Blockchain. ISPRS Int. J. Geo-Inf. 2022, 11, 409.
12. Weijie Wang, Annie Ulichney, and Charalampos Papamanthou. 2023. BalanceProofs: maintainable vector commitments with fast aggregation. In Proceedings of the 32nd USENIX Conference on Security Symposium (SEC '23). USENIX Association, USA, Article 247, 4409–4426.
13. Kurosawa, Kaoru, and Goichiro Hanaoka, eds. Public-Key Cryptography--PKC 2013: 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan, Feburary 26--March 1, 2013, Proceedings. Vol. 7778. Springer, 2013.
14. Peikert, Chris, Zachary Pepin, and Chad Sharp. "Vector and functional commitments from lattices." In Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part III 19, pp. 480-511. Springer International Publishing, 2021.
15. Kuszmaul, John. “Verkle Trees.”, 2019
16. C. Papamanthou, E. Shi, R. Tamassia, and K. Yi. Streaming authenticated data structures. In EUROCRYPT, pages 353–370. 2013.
17. Iavich, M., Gnatyuk, S., Arakelian, A., Iashvili, G., Polishchuk, Y., & Prysiazhnyy, D. (2021). Improved Post-quantum Merkle Algorithm Based on Threads. In Advances in Computer Science for Engineering and Education III 3 (pp. 454-464). Springer International Publishing.