VERKLE-FRI: НОВА АРХІТЕКТУРА ДЛЯ БЕЗСТАНОВИХ ТА КВАНТОВО-СТІЙКИХ ВЕКТОРНИХ ЗОБОВ’ЯЗАНЬ

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.