CONSTRUCTION OF LATTICE-BASED VECTOR COMMITMENTS FOR VERKLE STRUCTURES
DOI:
https://doi.org/10.56132/2791-3368-2026-2-66-75-85Keywords:
post-quantum cryptography, Verkle tree, lattice cryptography, cybersecurity, secure communication systemAbstract
This paper addresses the problem of constructing post-quantum authenticated data structures for secure distributed information systems operating under potential quantum and cyber threats. The primary focus is on the development of a Verkle tree based on lattice vector commitments, providing compact proof structures, support for local updates, and resistance to quantum attacks. Particular attention is given to the local update propagation mechanism, which enables modification of commitments and proofs without full recomputation of the tree. The proposed approach reduces computational overhead during data updates and improves the efficiency of distributed storage systems operating under limited computational resources and unstable communication channels. The proposed scheme can be applied in secure distributed storage systems, cyber defense infrastructures, and protected communication environments requiring post-quantum security guarantees.
Downloads
References
1. Algazy K., Sakan K., Nyssanbayeva S., Lizunov O. Syrga2: Post-Quantum Hash-Based Signature Scheme // Computation. 2024. Vol. 12. P. 1–17. DOI: 10.3390/computation12060125.
2. Lyubashevsky V., Nguyen N. K. Advances in Cryptology – ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5–9, 2022, Proceedings, Part IV // Advances in Cryptology – ASIACRYPT 2022. 2022. P. 95–125. DOI: 10.1007/978-3-031-22972-5_4.
3. Wee H., Wu D. J. Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis // Advances in Cryptology – ASIACRYPT 2023. Singapore: Springer Nature, 2023. P. 1–41.
4. Cini V., Malavolta G., Nguyen N. K., Wee H. Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup // Advances in Cryptology – CRYPTO 2024. Cham: Springer, 2024. LNCS. Vol. 14929. DOI: 10.1007/978-3-031-68403-6_7.
5. Fenzi G., Moghaddas H., Nguyen N. K. Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency // Journal of Cryptology. 2024. Vol. 37. No. 31. P. 1–92. DOI: 10.1007/s00145-024-09511-8.
6. Kuznetsov O., Frontoni E., Kuznetsova K., Arnesano M. Optimizing Merkle Proof Size Through Path Length Analysis: A Probabilistic Framework for Efficient Blockchain State Verification // Future Internet. 2025. Vol. 17. No. 2. P. 1–20. DOI: 10.3390/fi17020072.
7. Kuznetsov O., Kanonik D., Rusnak A., Yezhov A., Domin O. Adaptive Restructuring of Merkle and Verkle Trees for Enhanced Blockchain Scalability // Internet of Things. 2024. Vol. 27. P. 1–34. DOI: 10.1016/j.iot.2024.101315.
8. Kuszmaul J. Verkle Trees. MIT PRIMES Research Papers. Cambridge, MA: Massachusetts Institute of Technology, 2019. 12 p. Available online: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf (accessed on 10 April 2026).
9. Kuszmaul J. Verkle Trees: Ver (y Short Mer)kle Trees. Presentation at PRIMES Conference, Cambridge, MA: Massachusetts Institute of Technology, 19 May 2019. 40 slides. Available online:
https://math.mit.edu/research/highschool/primes/materials/2019/conf/12-5-Kuszmaul.pdf (accessed on 10 April 2026).
10. Catalano D., Fiore D. Vector Commitments and Their Applications // Public-Key Cryptography — PKC 2013. Berlin; Heidelberg: Springer, 2013. LNCS. Vol. 7778. P. 55–72. DOI: 10.1007/978-3-642-36362-7_5.
11. Kate A., Zaverucha G. M., Goldberg I. Constant-Size Commitments to Polynomials and Their Applications // Advances in Cryptology – ASIACRYPT 2010. Berlin; Heidelberg: Springer, 2010. LNCS. Vol. 6477. P. 177–194. DOI: 10.1007/978-3-642-17373-8_11.
12. Pathak V., Ruj S., van der Meyden R. Vector Commitment Design, Analysis, and Applications: A Survey // Cryptology ePrint Archive. Paper 2025/667. 2025. Available online.
