Verkle-Based HORST: A Scalable and Efficient Post-Quantum Digital Signature Scheme

Verkle-Based HORST: A Scalable and Efficient Post-Quantum Digital Signature Scheme

Speakers: Maksim Iavich, President at Scientific Cyber Security Association (SCSA), Professor and director at Cyber Security Centre, Caucasus University

Conference: DefCamp

YouTube: https://www.youtube.com/watch?v=-sptD2kXmu0

Overview

In an era rapidly approaching the dawn of practical quantum computing, the security foundations of modern digital communication are under existential threat. This talk, "Verkle-Based HORST: A Scalable and Efficient Post-Quantum Digital Signature Scheme," delivered by Maksim Iavich at DefCamp, addresses this critical challenge head-on. Professor Iavich, a distinguished figure in cybersecurity and head of the Cyber Security Centre at Caucasus University, presents an innovative approach to post-quantum digital signatures designed to be both secure against quantum adversaries and highly efficient in terms of signature size.

The core of Iavich's presentation lies in the development of a novel digital signature scheme that integrates the HORST (High-speed Optimized Representation of Signature Tree) one-time signature with a Verkle Tree structure, enhanced by lattice-based vector commitments. This hybrid scheme aims to overcome the limitations of existing post-quantum signature methods, particularly the large signature sizes associated with traditional Merkle tree constructions. By leveraging the cryptographic properties of Verkle trees and the robustness of lattice-based cryptography, the research proposes a significant reduction in signature size, specifically a 75% decrease compared to optimized NIST-standardized schemes like SPHINCS+. The talk serves as a vital exploration into the future of digital security, offering a tangible solution to secure digital communications in a post-quantum world.

Background

▶ Watch: Introduction and talk overview (0:00)

Modern cryptography relies on two fundamental pillars: symmetric and asymmetric (public-key) encryption. Symmetric cryptography, exemplified by the Advanced Encryption Standard (AES), uses a single shared secret key for both encryption and decryption. While highly efficient for data confidentiality, its primary challenge lies in secure key distribution. This problem is elegantly solved by asymmetric cryptography, which employs a pair of mathematically linked keys: a public key for encryption (or verification) and a private key for decryption (or signing). Widely used asymmetric algorithms like RSA, Diffie-Hellman (DH), and Elliptic Curve Cryptography (ECC) derive their security from the computational hardness of specific mathematical problems, such as integer factorization (RSA) or the discrete logarithm problem (DH, ECC).

Alongside encryption, hash functions are crucial for data integrity and digital signatures. A secure hash function, like SHA-256, maps arbitrary-length input to a fixed-size output (hash value or digest) and must exhibit properties like collision resistance, meaning it's computationally infeasible to find two different inputs that produce the same hash output. The talk highlights the historical progression of hash functions from MD5 (128-bit output, broken in 2004) to SHA-1 (160-bit, theoretically broken in 2013, practically in 2017) and the currently secure SHA-256 (256-bit). The birthday paradox demonstrates that collisions can be found with significantly less effort than brute-forcing, necessitating larger hash output sizes (e.g., 256 bits for classical security, 512 bits for post-quantum).

The advent of quantum computing fundamentally disrupts this cryptographic landscape. Algorithms like Shor's algorithm can efficiently solve the integer factorization and discrete logarithm problems, rendering RSA, DH, and ECC utterly insecure. Grover's algorithm can speed up brute-force attacks on symmetric keys and hash functions, effectively halving their security strength (e.g., a 256-bit AES key would offer only 128 bits of quantum security). This imminent threat has spurred global efforts to develop post-quantum cryptography (PQC) – cryptographic algorithms resistant to quantum attacks.

Professor Iavich traces the timeline of quantum supremacy claims, starting with Google's Sycamore processor in 2019, which reportedly solved a complex sampling task in 200 seconds, a feat estimated to take classical supercomputers millennia. While IBM challenged the exact timeline, the event marked a significant milestone. China followed suit, achieving quantum supremacy in both superconducting and photonic quantum computing with their Zukon Shinen processor, claiming it to be 10 million times faster than the fastest supercomputer and 1 million times faster than Sycamore. Today, China maintains a lead with Zukon Shinen 3.0 (105 superconducting qubits), followed by Google's Willow chip (144 qubits) and IBM's Heron processor (156 qubits). Japan's domestically made Osaka quantum computer (72 qubits) further underscores the global race.

In response to this looming threat, the National Institute of Standards and Technology (NIST) initiated a global competition to standardize post-quantum cryptographic algorithms. Four main families of PQC alternatives emerged: hash-based cryptography, code-based cryptography (e.g., McEliece), lattice-based cryptography, and multivariate public-key cryptography. NIST has already selected several schemes for standardization, including CRYSTALS-Kyber for encryption and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for digital signatures. The speaker notes that lattice-based cryptography, particularly the work of Chris Baker with whom he collaborated, is considered exceptionally robust due to its reliance on worst-case hardness problems. The talk specifically focuses on improving hash-based signature schemes, which often suffer from large signature sizes, a critical practical limitation.

Key Findings

▶ Watch: Google's quantum supremacy; China's advancements (20:15)

The central problem addressed by Professor Iavich's research is the trade-off between post-quantum security and practical efficiency, specifically concerning the signature size and tree height in hash-based digital signature schemes. While NIST has standardized hash-based schemes like SPHINCS+, their reliance on Merkle tree structures can lead to substantial signature sizes, which is undesirable for bandwidth-constrained environments or applications requiring compact data.

The key findings and contributions presented in the talk are:

1. Introduction of Verkle Trees for Digital Signatures: The research pioneers the application of Verkle Trees – a novel tree structure based on vector commitments – to construct digital signature schemes. Unlike traditional Merkle trees that use cryptographic hashing for node aggregation, Verkle trees use vector commitments, offering a significant advantage in proof size. The speaker highlights that their team is the first to create a digital signature scheme utilizing this tree structure.
2. Integration of HORST One-Time Signature: The proposed scheme integrates the HORST (High-speed Optimized Representation of Signature Tree) one-time signature scheme as the leaf-level signing mechanism within the Verkle tree structure. This combination leverages HORST's efficiency for individual message signing while using the Verkle tree for aggregate public key management.
3. Lattice-Based Vector Commitments for Post-Quantum Security: A crucial innovation is the use of lattice-based vector commitments within the Verkle tree. Traditional vector commitments might rely on problems like the Computational Diffie-Hellman (CDH) problem or RSA, which are vulnerable to quantum attacks. By integrating lattice-based commitments (specifically drawing from the work of Chris Baker), the entire Verkle tree structure becomes resistant to quantum adversaries, ensuring the scheme's end-to-end post-quantum security.
4. Significant Signature Size Reduction: The most compelling finding is the claimed 75% reduction in signature size when comparing the Verkle-based HORST scheme to optimized Merkle-based HORST schemes, such as SPHINCS+. This reduction is a direct consequence of the O(1) proof size offered by Verkle trees, contrasting sharply with the O(log N) proof size of Merkle trees.
5. Hybrid Security Model: The current iteration of the scheme operates in a hybrid security model, combining hash-based HORST (which is generally considered quantum-resistant) with lattice-based Verkle commitments. While offering robust security, the speaker acknowledges this hybrid nature as the main drawback, as the scheme's security depends on the unbroken status of both underlying cryptographic primitives. Future work aims to make the scheme entirely lattice-based.

In essence, the research offers a practical and efficient post-quantum digital signature scheme that addresses one of the major hurdles—signature size—in the transition to a quantum-resistant cryptographic infrastructure.

Technical Deep Dive

▶ Watch: Introducing Verkle trees for efficient digital signatures (38:30)

The proposed Verkle-Based HORST digital signature scheme builds upon the principles of hash-based signatures, specifically one-time and few-time signature schemes, while introducing a novel aggregation mechanism to enhance efficiency and scalability in a post-quantum context.

Foundations of Hash-Based Signatures

The talk begins by revisiting foundational hash-based signature schemes:

• Lamport One-Time Signature: This scheme generates 2*N* private keys (signature keys) for an N-bit hash output. These are hashed to produce 2*N* public keys (verification keys). To sign a message, the message is first hashed. For each bit of the message hash, a specific signature key from a pair is revealed (e.g., if the bit is '1', the second key is revealed; if '0', the first). The signature is the concatenation of these N revealed keys. Verification involves hashing the revealed keys and comparing them to the corresponding public keys. The drawback is a very large signature size and strictly one-time use.
• Winternitz One-Time Signature: To reduce signature size, Winternitz introduced hash chains. Instead of pairs of keys, it uses a single private key x and a public key generated by hashing x W times (where W is the Winternitz parameter). To sign, the message hash is split into log₂W pieces. If a piece's decimal value is C, the private key is hashed W-C times. The signature consists of these partially hashed keys. Verification requires hashing the signature pieces the remaining C times and comparing them to the W-hashed public keys. This reduces signature size but is still one-time.
• HORST (High-speed Optimized Representation of Signature Tree): This is a "few-time" signature scheme, more efficient than Lamport or Winternitz. It works by hashing the message and dividing the hash into log₂T parts, where T is a parameter (e.g., if T=16, divide into 4 chunks). Each chunk's decimal value Cᵢ directly indexes a specific private key SKᵢ. The signature is the concatenation of these T chosen private keys. Verification involves hashing each SKᵢ and comparing it to the pre-computed public key PKᵢ. While it "leaks" T private keys, security proofs allow for a concrete number of uses.

Merkle Tree for Multi-Time Signatures

To enable multiple signatures with these one-time/few-time schemes, the Merkle Tree is employed.

• Construction: A Merkle tree is built bottom-up. The leaves of the tree are the public keys (verification keys) of many individual one-time signature schemes (e.g., Lamport, Winternitz, or HORST). Each pair of adjacent leaves is concatenated and hashed, forming a parent node. This process continues upwards until a single root hash is obtained, which serves as the public key for the entire Merkle tree.
• Signing: To sign a message, one first generates a one-time signature using one of the leaf-level schemes. The signature then consists of:

1. The one-time signature itself.
2. The index of the leaf used.
3. All the sibling nodes (also called "flatter nodes" in the talk) on the path from the chosen leaf to the root.

• Verification: The verifier checks the one-time signature. Then, using the provided leaf index and sibling nodes, they recompute the path hashes up to the root. If the recomputed root matches the known public key, the signature is valid.
• Limitations: While effective, Merkle trees suffer from a signature size that grows logarithmically with the number of leaves (O(log N) for the proof path), which can still be substantial for large N. The talk also briefly mentions k-ary Merkle trees (e.g., ternary, K=3), which reduce tree height but often increase signature size.

Verkle Tree: The Core Innovation

The research introduces the Verkle Tree as a more efficient alternative to the Merkle tree for aggregating public keys.

• Vector Commitments: Instead of cryptographic hash functions, Verkle trees utilize vector commitments. A vector commitment allows committing to a vector of values (e.g., the public keys of the leaf-level signatures) and later proving that a specific element at a specific position is part of that committed vector, with a very small proof size. The root of the Verkle tree is a single vector commitment to all underlying values.
• Proof Size: The primary advantage of Verkle trees is their significantly smaller proof size. While Merkle trees require O(log N) data (the sibling nodes) to prove inclusion, Verkle trees can achieve O(1) proof size (or linear, O(1), depending on settings as stated in the talk, referring to the number of elements in the vector, not the tree depth), making them highly efficient.
• Post-Quantum Security of Verkle Commitments: A critical aspect is ensuring the post-quantum security of the vector commitments themselves. Traditional vector commitments might rely on problems like the Computational Diffie-Hellman (CDH) problem or RSA, which are vulnerable to quantum attacks. The speaker emphasizes that their team integrated lattice-based vector commitments, drawing upon the work of leading experts like Chris Baker. This ensures that the Verkle tree's structure and its proofs are resistant to quantum adversaries.

Verkle-Based HORST Scheme Construction

The proposed scheme combines these elements:

1. Key Generation: Generate secret keys for many HORST one-time signature schemes.
2. Leaf Computation (Vector Commitments): Instead of hashing the HORST public keys to form Merkle tree leaves, the public keys are used as inputs to the lattice-based vector commitment scheme to compute the "leaves" of the Verkle tree.
3. Tree Construction: The vector commitments are aggregated upwards, forming intermediate commitments, until a final root vector commitment is obtained. This root serves as the public key for the entire Verkle-based HORST scheme. During this process, corresponding proofs for the vector commitments are calculated.
4. Signing: To sign a message:

• A HORST one-time signature is generated for the message using one of the underlying HORST schemes.
• The signature includes the HORST one-time signature, the index of the used HORST public key, and the relevant Verkle commitment proofs that demonstrate the public key's inclusion in the root vector commitment.

1. Verification: To verify:

• First, the HORST one-time signature is verified using its corresponding public key.
• Second, the Verkle commitment proofs are used to verify that the HORST public key is indeed committed to by the scheme's public root vector commitment. If both checks pass, the signature is valid.

Efficiency and Drawbacks

The scheme achieves a 75% reduction in signature size compared to optimized Merkle-based HORST schemes (like SPHINCS+). While verification time is small, the calculation time for generating signatures can be slightly less efficient due to the overhead of vector commitment proofs.

A notable drawback acknowledged by the speaker is the hybrid nature of the current scheme: it relies on both the quantum resistance of hash-based HORST and the quantum resistance of lattice-based vector commitments. If either of these underlying primitives were to be broken by a quantum attack, the entire scheme's security would be compromised. The research team is actively working to develop a fully lattice-based version to mitigate this potential vulnerability.

Demo / Proof of Concept

▶ Watch: Verkle-Based HORST reduces signature size by 75% (43:00)

The talk primarily focused on the theoretical construction, comparative analysis, and cryptographic properties of the Verkle-based HORST scheme rather than a live demonstration of its implementation. Professor Iavich meticulously explained the conceptual flow and technical underpinnings of the proposed digital signature scheme, detailing how it leverages Verkle trees and lattice-based vector commitments to achieve post-quantum security and reduced signature size.

While no specific tool or live code demonstration was presented, the technical deep dive provided a clear outline of how such a proof of concept would function. In a practical implementation, the process would involve:

1. Setup Phase: Generating a large set of private keys for the underlying HORST one-time signature schemes. These HORST public keys would then be used to compute the leaves of the Verkle tree using lattice-based vector commitments. The Verkle tree would be constructed bottom-up, aggregating these commitments until a single root vector commitment (the scheme's public key) is derived, along with all necessary inclusion proofs.
2. Signing Phase: When a message needs to be signed, one of the available HORST one-time signature instances would be used to generate a signature for the message's hash. The final signature bundle would then combine this HORST signature with the pre-computed Verkle commitment proofs that validate the HORST public key's inclusion in the overall Verkle tree public key.
3. Verification Phase: A verifier would first independently verify the HORST one-time signature. Subsequently, they would use the provided Verkle commitment proofs to cryptographically confirm that the HORST public key used for signing is indeed part of the publicly known root vector commitment. The successful completion of both steps would validate the digital signature.

The speaker emphasized the theoretical efficiency gains, particularly the 75% reduction in signature size, which is a significant metric in a proof-of-concept for PQC schemes. The discussion included comparative data, highlighting the smaller signature size and reasonable verification times of their scheme compared to existing Merkle-based approaches like SPHINCS+. The ongoing research to develop a fully lattice-based version further suggests that practical implementations are a key future goal.

Defensive Implications

▶ Watch: Strategy for hybrid classical and post-quantum security (47:40)

The implications of Maksim Iavich's Verkle-Based HORST research are profound for cybersecurity defenders, emphasizing the urgent need for a proactive transition to post-quantum cryptography (PQC).

1. Immediate Threat of "Gather Today, Break Tomorrow": The speaker reiterates the critical warning that encrypted communications secured with classical asymmetric algorithms (RSA, ECC, Diffie-Hellman) are vulnerable to future decryption by quantum computers. Adversaries can "gather today" vast amounts of encrypted data and store it, anticipating the arrival of powerful quantum machines to "break tomorrow." This necessitates immediate action to protect long-term sensitive data.
2. Mandate for Hybrid Cryptography: NIST's directive for organizations to begin integrating PQC standards, with a full transition expected within approximately 10 years, underscores the urgency. Defenders should adopt a hybrid mode for both encryption and digital signatures. This involves using both classical (e.g., AES-256 for encryption, SHA-256-based signatures) and post-quantum algorithms concurrently. As Professor Iavich explains, "If somebody breaks postquantum, classical will still be in. If somebody breaks classical, postquantum will still be in." This dual-layer approach provides resilience against unforeseen weaknesses in either classical or PQC schemes during the transition period.
3. Addressing Signature Size Challenges: One of the significant hurdles for PQC adoption, particularly for hash-based signatures, is the often-large signature size. Schemes like Verkle-based HORST directly tackle this, demonstrating a 75% reduction compared to current standards. For defenders, this means that integrating PQC signatures into existing protocols and applications might be more feasible without drastically impacting bandwidth, storage, or processing overhead. This efficiency gain is crucial for widespread adoption in areas like firmware signing, secure boot, certificate chains, and blockchain applications.
4. Understanding Underlying PQC Primitives: The hybrid nature of Verkle-based HORST, combining hash-based HORST with lattice-based vector commitments, highlights the importance for defenders to understand the security assumptions of all underlying primitives. While this scheme is a step towards a fully quantum-resistant future, its current security relies on both hash functions remaining collision-resistant (even against quantum attacks that reduce effective collision resistance) and lattice problems remaining hard. Defenders should stay informed about ongoing research and potential vulnerabilities in both hash-based and lattice-based cryptography.
5. Staying Updated with NIST Standardization: The NIST Post-Quantum Cryptography Standardization process is the authoritative source for quantum-resistant algorithms. Defenders must continuously monitor NIST's selections and recommendations (e.g., CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, SPHINCS+). Research like Verkle-based HORST contributes to the evolving landscape and may inform future iterations or alternatives to these standards.
6. Research and Development Focus: The ongoing work to make Verkle-based HORST fully lattice-based signals a broader trend in PQC research to reduce reliance on hybrid security models where possible. Defenders should encourage and support research into more consolidated, single-primitive PQC solutions, as these could simplify security analysis and deployment in the long run.
7. Infrastructure Assessment: Organizations must begin assessing their current cryptographic infrastructure to identify where classical asymmetric cryptography is deployed and plan for its replacement or augmentation with PQC. This includes PKI systems, VPNs, secure communication protocols (HTTPS/TLS), code signing, and identity management systems. The insights from this talk provide valuable data points for evaluating potential PQC signature candidates based on their efficiency characteristics.

In summary, the Verkle-Based HORST scheme provides a concrete example of how cryptographic innovation is addressing the practical deployment challenges of PQC. Defenders must recognize the urgency, embrace hybrid solutions, and leverage efficient new schemes to secure their systems against the quantum threat.

Key Takeaways

• Imminent Quantum Threat: Quantum computers, particularly with advances in quantum supremacy demonstrated by Google and China, pose an existential threat to all current asymmetric cryptographic systems (RSA, ECC, Diffie-Hellman), necessitating an urgent transition to post-quantum cryptography.
• Hash-Based Signatures and Their Limitations: Hash-based digital signature schemes like SPHINCS+ are quantum-resistant and NIST-standardized, but often suffer from large signature sizes and Merkle tree structures that result in O(log N) proof sizes, which can be inefficient for practical deployment.
• Verkle Trees for Efficiency: Verkle trees, which utilize vector commitments instead of cryptographic hashing, offer a breakthrough in efficiency by enabling significantly smaller proof sizes (O(1) or linear, depending on specific settings) compared to traditional Merkle trees, making them ideal for reducing signature length.
• Verkle-Based HORST Scheme: The presented Verkle-based HORST scheme combines the HORST one-time signature with a Verkle tree structure, crucially using lattice-based vector commitments to ensure its post-quantum security against quantum attacks that could break CDH or RSA-based commitments.
• Significant Signature Size Reduction: This novel scheme achieves a remarkable 75% reduction in signature size compared to optimized Merkle-based HORST schemes (like SPHINCS+), addressing a major practical challenge for widespread post-quantum cryptography adoption.
• Hybrid Deployment Strategy: For immediate protection, a hybrid cryptographic approach is recommended for both encryption and digital signatures, where classical and post-quantum algorithms are used concurrently. This provides robust security even if one of the underlying cryptographic families is compromised.
• Future Research Towards Fully Lattice-Based: The current scheme's security is hybrid (hash-based HORST + lattice-based Verkle commitments). Ongoing research aims to develop a fully lattice-based version of the scheme to eliminate this dependency and potentially enhance its overall security posture.

About the Speaker(s)

Maksim Iavich is a distinguished figure in the field of cybersecurity and cryptography. He serves as the President of the Scientific Cyber Security Association (SCSA), which he describes as the largest cybersecurity organization in his region of Georgia. Academically, Professor Iavich is a Professor and Director of the Cyber Security Centre at Caucasus University, where he leads a substantial research and educational initiative. His contributions to the scientific community were further recognized this year by his appointment as a Corresponding Member of the Georgia National Scientific Academy.

Professor Iavich is a veteran speaker at DefCamp, having presented at the conference since 2018, underscoring his consistent engagement with the cybersecurity community. His expertise extends particularly to post-quantum cryptography, where he has been actively involved in research since 2013, following early developments in quantum computing. Notably, he spent time in Michigan as a researcher with Chris Baker, a leading expert in lattice-based cryptography, a field considered highly promising for post-quantum security. This collaboration highlights his commitment to advancing the state-of-the-art in quantum-resistant cryptographic solutions.