VERKLE-FRI: A NOVEL ARCHITECTURE FOR STATELESS AND QUANTUM-RESISTANT VECTOR COMMITMENTS

Giorgi Akhalaia, Maksim Iavich, Razvan Bocu

Abstract


The subject matter of the article is the cryptographic integrity of digital authentication systems facing quantum computing threats, specifically focusing on post-quantum alternatives and efficient authenticated data structures. The goal is to design and formally analyze VERKLE-FRI—a hybrid architecture synthesizing Verkle tree proof-size reduction with FRI-based quantum-resistant commitments, establishing a scalable, stateless, and quantum-secure framework. The tasks are: analyze limitations of hash-based signatures and Merkle trees; evaluate polynomial commitment schemes (KZG, Bulletproofs, FRI, lattice-based); propose a hybrid Verkle-FRI design; develop a formal security proof against classical and quantum adversaries; execute complexity analysis with concrete implementation parameters. The methods used are: theoretical cryptographic analysis, formal security modeling via reductionist proofs, algebraic methods over finite fields, polynomial interpolation, random oracle model, FRI protocol with DEEP-FRI optimization, Merkle trees, vector commitments, and asymptotic complexity analysis. The following results were achieved: a novel architecture where Verkle node vectors are polynomial-encoded, committed via Merkle trees over FRI codewords, and verified through FRI with out-of-domain sampling. A formal proof establishes λ-bit quantum security using 2λ-bit hash functions. Complexity yields proof size O(λ log² N), prover time O(λ N log N), and verifier time O(λ log N). Concrete 128-bit quantum parameters include SHA3-512, field size ≈2²⁵⁵, branching factor 256, and 128 FRI rounds, achieving soundness error ≤2⁻¹²⁷. For a concrete benchmark authenticating 2²⁶ elements, a traditional Merkle proof requires ≈0.8 KB, whereas our VERKLE-FRI proof requires ≈180 KB. While larger, this provides quantum resistance and eliminates the trusted setup, a critical trade-off for long-term security. Conclusions. Scientific novelty consists in: 1) the first hybrid Verkle-FRI architecture replacing pairing-based assumptions with hash-based proximity testing; 2) a formal security proof reducing security to hash collision resistance and FRI soundness; 3) quantified efficiency-security trade-offs; 4) a viable pathway for quantum-resistant infrastructure in blockchains, software distribution, and government communications.


Keywords


Post-quantum Security; Cryptography; FRI; Polynomial Commitments; Digital Hash-Based Signatures.

References


Li, L., Lu, X., & Wang, K. Hash-based signature revisited. Cybersecurity, 2022, vol. 5, no. 1, article no. 13. DOI: 10.1186/s42400-022-00117-w.

Pacurar, C. M., Bocu, R., & Iavich, M. An analysis of existing hash-based post-quantum signature schemes. Symmetry, 2025, vol. 17, no. 6, article no. 919. DOI: 10.3390/sym17060919.

Iavich, M., Kuchukhidze, T., & Bocu, R. A post-quantum digital signature using Verkle trees and lattices. Symmetry, 2023, vol. 15, no. 12, article no. 2165. DOI: 10.3390/sym15122165.

NIST. Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process. NIST IR 8454, National Institute of Standards and Technology, 2024. DOI: 10.6028/NIST.IR.8454.

Thoma, J. P., Hartlief, D., & Güneysu, T. Agile acceleration of stateful hash-based signatures in hardware. ACM Transactions on Embedded Computing Systems, 2024, vol. 23, no. 2, article no. 29. DOI: 10.1145/3631534.

Fenzi, G., Moghaddas, H., & Nguyen, N. K. Lattice-based polynomial commitments: towards asymptotic and concrete efficiency. Journal of Cryptology, 2024, vol. 37, no. 4, article no. 31. DOI: 10.1007/s00145-024-09511-8.

Iavich, M., & Kapalova, N. Asymmetric post-quantum digital signature scheme with k-ary Verkle trees. Symmetry, 2025, vol. 17, no. 3, article no. 437. DOI: 10.3390/sym17030437.

Nutu, M., Akhalaia, G., Bocu, R., & Iavich, M. An extended survey concerning the vector commitments. Applied Sciences, 2025, vol. 15, no. 17, article no. 9510. DOI: 10.3390/app15179510.

Algazy, K. T., Sakan, K. S., Nyssanbayeva, S. E., & Khompysh, A. Polynomial commitment in a Verkle tree based on a non-positional polynomial notation. Computers, Materials & Continua, 2025, vol. 83, no. 2, pp. 885–905. DOI: 10.32604/cmc.2025.065085.

Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. Fast Reed-Solomon interactive oracle proofs of proximity. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, July 9–13, 2018, pp. 14:1–14:17. DOI: 10.4230/LIPIcs.ICALP.2018.14.

Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., & Ward, N. P. Aurora: transparent succinct arguments for R1CS. Advances in Cryptology – EUROCRYPT 2019, Darmstadt, Germany, May 19–23, 2019, pp. 103–128. DOI: 10.1007/978-3-030-17656-3_4.

Chiesa, A., Ojha, D., & Spooner, N. Fractal: post-quantum and transparent recursive proofs from holography. Advances in Cryptology – EUROCRYPT 2020, Zagreb, Croatia, May 10–14, 2020, pp. 769–793. DOI: 10.1007/978-3-030-45724-2_26.

Guo, Y., Liu, X., Huang, K., Qu, W., Tao, T., & Zhang, J. DeepFold: efficient multilinear polynomial commitment from Reed-Solomon code and its application to zero-knowledge proofs. Proceedings of the 34th USENIX Security Symposium, Seattle, WA, USA, August 13–15, 2025, pp. 3497–3514. Available at: https://www.usenix.org/conference/usenixsecurity25/presentation/guo (accessed March 13, 2026).

Ben-Sasson, E., Goldberg, L., Kopparty, S., & Saraf, S. DEEP-FRI: sampling outside the box improves soundness. Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Seattle, WA, USA, January 12–14, 2020, article no. 75, pp. 75:1–75:29. DOI: 10.4230/LIPIcs.ITCS.2020.75.




DOI: https://doi.org/10.32620/reks.2026.2.17

Refbacks

  • There are currently no refbacks.