Maksim Iavich; Tamari Kuchukhidze; Razvan Bocu

A Novel Verkle Tree-based Post-quantum Digital Signature System with Enhanced Random Number Generation

PDF (869KB), PP.19-36

Views: 0 Downloads: 0

Author(s)

Maksim Iavich ¹ Tamari Kuchukhidze ^1,* Razvan Bocu ²

1. Department of Computer Science, Caucasus University, 0102, Georgia

2. Department of Mathematics and Computer Science, Transilvania University of Brasov, 500036 Brasov, Romania

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2025.04.02

Received: 28 Dec. 2024 / Revised: 12 Feb. 2025 / Accepted: 8 Apr. 2025 / Published: 8 Aug. 2025

Index Terms

Quantum Cryptography, Post-quantum Cryptography, Merkle, Vector Commitments, Lattice-based Vector Commitments, Cryptographical Application, Verkle Tree, Postprocessing

Abstract

The security of public key cryptosystems has become a major concern due to recent developments in the field of quantum computing. Despite efforts to enhance defenses against quantum attacks, current methods are impractical due to safety and efficacy concerns. A recent study explores hash-based digital signature methods and evaluates their effectiveness using Merkle trees. Furthermore, novel approaches based on Verkle trees and vector commitments have been studied to reduce quantum threats.
First, we introduce a post-quantum digital signature system that combines vector commitments based on lattices with Verkle trees. This architecture optimizes traditional Merkle tree architecture by preserving resistance to quantum attacks while improving cryptographic proofs. Second, in order to ensure secure initial seed generation without sacrificing operational viability, we create a hybrid random number generation framework that combines quantum random number generation (QRNG) with pseudorandom approaches. We provide a detailed analysis of generating random numbers in our article, which makes it easier to build a post quantum cryptosystem that uses our generator to provide initial random values. Our system is notable for its robust security against quantum threats, speed, and efficiency.

Cite This Paper

Maksim Iavich, Tamari Kuchukhidze, Razvan Bocu, "A Novel Verkle Tree-based Post-quantum Digital Signature System with Enhanced Random Number Generation", International Journal of Computer Network and Information Security(IJCNIS), Vol.17, No.4, pp.19-36, 2025. DOI:10.5815/ijcnis.2025.04.02

Reference

[1]Chen, Lily, Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray A. Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. Vol. 12. Gaithersburg, MD, USA: US Department of Commerce, National Institute of Standards and Technology, 2016.
[2]Shor, P. W. (2002, May). Introduction to quantum algorithms. In Proceedings of Symposia in Applied Mathematics (Vol. 58, pp. 143-160).
[3]Peikert, C. (2016). A decade of lattice cryptography. Foundations and trends® in theoretical computer science, 10(4), 283-424.
[4]Khalid, A., Oder, T., Valencia, F., O'Neill, M., Güneysu, T., & Regazzoni, F. (2018, May). Physical protection of lattice-based cryptography: Challenges and solutions. In Proceedings of the 2018 on Great Lakes Symposium on VLSI (pp. 365-370).
[5]Biswas, Bhaskar, and Nicolas Sendrier. "McEliece cryptosystem implementation: Theory and practice." In Post-Quantum Cryptography: Second International Workshop, PQCrypto 2008 Cincinnati, OH, USA, October 17-19, 2008 Proceedings 2, pp. 47-62. Springer Berlin Heidelberg, 2008.
[6]Buchmann, Johannes, Erik Dahmen, and Michael Szydlo. "Hash-based digital signature schemes." In Post-quantum cryptography, pp. 35-93. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. https://doi.org/10.1007/978-3-540-88702-7_3
[7]Anita Murmu, Piyush Kumar, "A Novel GAN with DNA Sequences and Hash-based Approach for Improving Medical Image Security", International Journal of Image, Graphics and Signal Processing, Vol.16, No.6, pp. 72-86, 2024.
[8]Joseph, D., Misoczki, R., Manzano, M., Tricot, J., Pinuaga, F. D., Lacombe, O., ... & Hansen, R. (2022). Transitioning organizations to post-quantum cryptography. Nature, 605(7909), 237-243.
[9]Buchmann, J., Dahmen, E., Hülsing, A. (2011). XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions. In: Yang, BY. (eds) Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science, vol 7071. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25405-5_8
[10]Cao, Y., Wu, Y., Qin, L., Chen, S., & Chang, C. H. (2022). Area, time and energy efficient multicore hardware accelerators for extended Merkle signature scheme. IEEE Transactions on Circuits and Systems I: Regular Papers, 69(12), 4908-4918.
[11]Buchmann, J. A., Butin, D., Göpfert, F., & Petzoldt, A. (2016). Post-quantum cryptography: state of the art. The New Codebreakers: Essays Dedicated to David Kahn on the Occasion of His 85th Birthday, 88-108.
[12]Lin, K. W., & Chen, Y. C. (2023, July). A File Verification Scheme Based on Verkle Trees. In 2023 International Conference on Consumer Electronics-Taiwan (ICCE-Taiwan) (pp. 295-296). IEEE.
[13]Catalano, D., & Fiore, D. (2013). Vector commitments and their applications. In Public-Key Cryptography–PKC 2013: 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16 (pp. 55-72). Springer Berlin Heidelberg.
[14]Kuszmaul, J., 2019. Verkle trees. Verkle Trees, 1(1).
[15]Wang, H., Yiu, S. M., Zhao, Y., & Jiang, Z. L. (2024, April). Updatable, aggregatable, succinct mercurial vector commitment from lattice. In IACR International Conference on Public-Key Cryptography (pp. 3-35). Cham: Springer Nature Switzerland.
[16]Alagic, G. (2024). Status report on the fourth round of the NIST Post-Quantum Cryptography Standardization Process. https://doi.org/10.6028/nist.ir.8545
[17]PUB, F. (2000). Digital signature standard (DSS). Fips pub, 186-192.
[18]Iavich, M., Kuchukhidze, T., & Bocu, R. (2023, March). A Post-quantum Cryptosystem with a Hybrid Quantum Random Number Generator. In International Conference on Advanced Information Networking and Applications (pp. 367-378). Cham: Springer International Publishing.
[19]Zentai, D. (2020). On the efficiency of the Lamport Signature Scheme. Land Forces Academy Review, 25(3), 275-280.
[20]Dods, C., Smart, N. P., & Stam, M. (2005). Hash based digital signature schemes. In Cryptography and Coding: 10th IMA International Conference, Cirencester, UK, December 19-21, 2005. Proceedings 10 (pp. 96-115). Springer Berlin Heidelberg.
[21]Srivastava, V., Baksi, A., & Debnath, S. K. (2023). An overview of hash based signatures. Cryptology ePrint Archive.
[22]Merkle, R. C. (2003, May). A DIGITAL SIGNATURE BASED ON A CONVENTIONAL ENCRYPTION FUNCTION. In Advances in Cryptology-CRYPTO'87: Proceedings (Vol. 293, p. 369). Springer.
[23]Qu, Q., Nurgaliev, I., Muzammal, M., Jensen, C. S., & Fan, J. (2019). On spatio-temporal blockchain query processing. Future generation computer systems, 98, 208-218.
[24]Gorbunov, S., Reyzin, L., Wee, H., & Zhang, Z. (2020, October). Pointproofs: Aggregating proofs for multiple vector commitments. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (pp. 2007-2023).
[25]Lin, D., & Sako, K. (2019, April). Public-Key Cryptography–PKC 2019. In 22nd IACR international conference on practice and theory of public-key cryptography. Beijing, China (pp. 14-17).
[26]Iavich, M., Kuchukhidze, T., & Bocu, R. (2023). A Post-Quantum Digital Signature Using Verkle Trees and Lattices. Symmetry, 15(12), 2165.
[27]Iavich, M., Gagnidze, A., Iashvili, G., Gnatyuk, S., & Vialkova, V. (2019). Lattice based merkle. In IVUS (pp. 13-16).
[28]Peikert, C., Pepin, Z., & Sharp, C. (2021). 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.
[29]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.
[30]Iavich, M., Iashvili, G., Gnatyuk, S., Tolbatov, A., & Mirtskhulava, L. (2021, October). Efficient and Secure Digital Signature Scheme for Post Quantum Epoch. In International Conference on Information and Software Technologies (pp. 185-193). Springer, Cham.
[31]Kabiri Chimeh, M., Heywood, P., Pennisi, M., Pappalardo, F., & Richmond, P. (2019). Parallelisation strategies for agent based simulation of immune systems. BMC bioinformatics, 20, 1-14.
[32]Wichmann, B. A., & Hill, I. D. (2006). Generating good pseudo-random numbers. Computational Statistics & Data Analysis, 51(3), 1614-1622.
[33]Lambić, D., & Nikolić, M. (2017). Pseudo-random number generator based on discrete-space chaotic map. Nonlinear Dynamics, 90(1), 223-232.
[34]Mandal, K., Fan, X., & Gong, G. (2016). Design and implementation of warbler family of lightweight pseudorandom number generators for smart devices. ACM Transactions on Embedded Computing Systems (TECS), 15(1), 1-28.
[35]Moizuddin, M., Winston, J., & Qayyum, M. (2017, March). A comprehensive survey: quantum cryptography. In 2017 2nd international conference on anti-cyber crimes (ICACC) (pp. 98-102). IEEE.
[36]Subramani, S., & Svn, S. K. (2023). Review of security methods based on classical cryptography and quantum cryptography. Cybernetics and Systems, 1-19.
[37]Fürst, H., Weier, H., Nauerth, S., Marangon, D. G., Kurtsiefer, C., & Weinfurter, H. (2010). High speed optical quantum random number generation. Optics express, 18(12), 13029-13037.
[38]Ma, X., Yuan, X., Cao, Z., Qi, B., & Zhang, Z. (2016). Quantum random number generation. npj Quantum Information, 2(1), 1-9.
[39]Subramani, S., & Svn, S. K. (2023). Review of security methods based on classical cryptography and quantum cryptography. Cybernetics and Systems, 1-19.
[40]Gnatyuk, S., Okhrimenko, T., Iavich, M., & Berdibayev, R. (2019, October). Intruder control mode simulation of deterministic quantum cryptography protocol for depolarized quantum channel. In 2019 IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S&T) (pp. 825-828). IEEE
[41]Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., & Mohaisen, A. (2018). RFC 8391: XMSS: eXtended Merkle Signature Scheme.
[42]Iavich, M., Gnatyuk, S., Odarchenko, R., Bocu, R., & Simonov, S. (2021, May). The novel system of attacks detection in 5G. In International Conference on Advanced Information Networking and Applications (pp. 580-591). Springer, Cham.
[43]Iavich, M., Kuchukhidze, T., Gnatyuk, S., & Fesenko, A. (2021). Novel certification method for quantum random number generators. International Journal of Computer Network and Information Security, 13(3), 28-38.
[44]Jacak, M. M., Jóźwiak, P., Niemczuk, J., & Jacak, J. E. (2021). Quantum generators of random numbers. Scientific Reports, 11(1), 16108.
[45]Ritterhoff, S., Bitzer, S., Karl, P., Maringer, G., Schamberger, T., Schupp, J., ... & Weger, V. (2023). Submission to the NIST Post-Quantum Cryptography Standardization Process Algorithm Specifications and Supporting Documentation.
[46]Jackson, K. A., Miller, C. A., & Wang, D. (2024, April). Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 418-446). Cham: Springer Nature Switzerland.
[47]Espitau, T., Tibouchi, M., Wallet, A., & Yu, Y. (2022, August). Shorter hash-and-sign lattice-based signatures. In Annual International Cryptology Conference (pp. 245-275). Cham: Springer Nature Switzerland.
[48]Kamal, A., Ahmad, K., Hassan, R., & Khalim, K. (2021). NTRU Algorithm: Nth Degree truncated polynomial ring units. In Functional Encryption (pp. 103-115). Cham: Springer International Publishing.

International Journal of Computer Network and Information Security (IJCNIS)