This paper presents a novel Verkle signature scheme that integrates a SHAKE-based deterministic random bit generator (DRBG) and quantum random number generator (QRNG) to achieve eficient, scalable, and postquantum secure digital signatures. The proposed design addresses the ineficiencies of traditional one-time signature schemes, which sufer from high storage and key management overheads. By using a QRNG for seed initialization and SHAKE-based PRNG for deterministic key generation, the system produces on-demand one-time key pairs without requiring persistent storage. These keys are structured within a Verkle tree, leveraging vector commitments to reduce proof sizes and optimize verification. The resulting architecture ofers strong security against quantum attacks, forward secrecy, and reduced computational and memory costs, making it suitable for deployment in constrained or large-scale environments. Our approach ensures compatibility with post-quantum cryptographic requirements while maintaining practical eficiency.
The rise of quantum computing introduces a fundamental shift in the landscape of information security.
Many widely deployed cryptographic protocols rely on the presumed dificulty of problems such as
integer factorization and discrete logarithms. These assumptions underpin schemes like RSA, DSA, and
elliptic curve cryptography (ECC), which are at the heart of modern secure communication systems.
However, advances in quantum algorithms, most notably Shor’s algorithm, have demonstrated that these
mathematical problems can be eficiently solved using quantum computers. As a result, current public
key infrastructures would become insecure in the presence of a scalable quantum adversary [
This imminent threat has initiated a global efort to design post-quantum cryptographic (PQC)
algorithms that can remain secure even against adversaries equipped with quantum capabilities [
In addition to structural improvements through Verkle trees, we propose a novel approach to
randomness and key generation. Instead of relying solely on stored key material, our scheme introduces a hybrid
mechanism that combines a true quantum random number generator (QRNG) with a SHAKE-based
deterministic random bit generator (DRBG) [
This approach resolves the limitations of key storage in one-time signature schemes by allowing reproducible key generation from a secure seed. Keys are generated only when needed, enabling the system to maintain strong cryptographic guarantees while minimizing storage and memory overhead. Moreover, using SHAKE-based DRBG as a core component aligns the construction with established postquantum standards, increasing the scheme’s compatibility with evolving cryptographic frameworks.
The primary objectives of this research are outlined as follows: • To propose a digital signature scheme that integrates Verkle trees for reduced proof size and faster verification compared to traditional Merkle constructions. • To design a key generation and randomness framework that combines quantum entropy from QRNG with deterministic pseudorandomness from SHAKE-based DRBG, enhancing unpredictability and scalability. • To eliminate the need for persistent storage of large key sets in one-time signature systems by enabling dynamic and deterministic key generation. • To demonstrate how the use of vector commitments within Verkle trees supports eficient aggregation and verification, reducing the computational burden on verifying parties. • To lay out a cryptographically secure framework suitable for long-term post-quantum applications, including digital identity, secure messaging, and blockchain infrastructure, without the inclusion of implementation-specific performance measurements.
This paper presents a forward-looking signature construction designed to withstand the impact of quantum computing while remaining eficient and scalable. By combining Verkle trees with hybrid randomness generation, the scheme achieves both theoretical soundness and practical adaptability. It is well-positioned for adoption in scenarios where security, compactness, and quantum resistance are essential.
One-time signature (OTS) schemes provide secure digital signatures for a single message per key pair. A classical example is the Lamport-Difie scheme, which uses hash functions and random bit strings for secure message authentication. The private key consists of 2 random bit strings: To sign a message , a digest 0, 1 is computed using a hash function :
= (0[0], 0[
= (0[0], 0[
The public key is derived by applying a one-way function to each element of the private key: = ( ) = (0, 1, . . . , −1 ) . (1) (2) (3) The signature consists of one value from each key pair, selected according to the corresponding bit in the message digest:
sign = (0[0], 1[1], . . . , −1 [−1 ]) .
Verification involves applying the function to each value in the signature and comparing the result with the corresponding public key entries:
︀( (sign0), (sign1), . . . , (sign−1 )︀) = (0[0], 1[1], . . . , −1 [−1 ]) .
Although secure, this approach is limited by the fact that each key can only be used once. To improve eficiency, schemes like Winternitz OTS (W-OTS) allow multiple bits to be signed with fewer hash operations.
To overcome the key reuse limitation of OTS schemes, Merkle trees are used to scale signature
systems [
= ℎ (2, 2+1) . (4) (5) (6) (7)
The root of the tree becomes the overall public key of the system. When a message is signed, a one-time key is used along with an authentication path-a sequence of sibling nodes that allows the verifier to reconstruct the root of the tree.
To verify the signature, the verifier checks the one-time signature, reconstructs the root using the authentication path, and compares it with the known public key.
While Merkle trees ofer scalability, they come with trade-ofs. The signer must store a large number of private keys, and the signature includes multiple hash values in the authentication path, which increases its size as the tree height grows.
Figure 1 shows an example of a Merkle tree with height of = 3.
Cryptographic protocols designed for the post-quantum era must balance strong security with practical eficiency, particularly in terms of memory usage and verification speed. Verkle trees provide an efective alternative to Merkle trees by enabling much smaller proofs while maintaining integrity and verifiability. This makes them especially useful in systems where compactness and verification speed are critical, such as blockchain networks and resource-constrained cryptographic devices.
A Verkle tree is a hierarchical data structure that uses vector commitments to commit to a large set of values in a compact and eficient way. Each internal node in the tree aggregates several child values or commitments into a single root using a commitment scheme that allows selective opening. Assume a node holds k values denoted by:
0, 1, . . . , −1 .
A commitment is created over this collection using a vector commitment function: = VectorCommit (0, 1, . . . , −1 ) .
This commitment serves as the representation of all values at that node. To prove that a particular value is part of the committed set, an opening proof is generated that reveals only and proves its inclusion without disclosing the other values.
In the same manner, internal nodes can commit to the vector commitments of their children. This recursive structure continues up the tree, and the final commitment at the top level becomes the root: (8) (9) Root = VectorCommit ( 1, 2, . . . , ) . (10) This root serves as the digest of the entire Verkle tree and is used for verification in applications such as digital signatures or data integrity proofs.
Verkle trees ofer significant advantages compared to classical Merkle trees. In a Merkle tree, to prove that a leaf is part of the tree, the prover must provide all sibling hashes along the path to the root. This leads to a proof size that grows with the height of the tree. In contrast, Verkle trees allow each internal node to cover many values. As a result, the depth of the tree decreases, and proofs consist of fewer elements. The proof includes one opening per vector commitment along the path, rather than full sibling sets.
Let be the branching factor of the tree and ℎ its height. In this case, proof size scales approximately with log, where is the number of committed values. A larger branching factor reduces the depth of the tree and, consequently, the number of openings required in a proof.
This approach brings practical benefits: • Significantly smaller proofs; • Faster verification time due to fewer operations; • Better scalability in large systems.
Verkle trees are well aligned with the goals of post-quantum cryptography. Vector commitments can be constructed using assumptions that are considered secure against quantum adversaries, such as lattice-based problems or hash-based constructions.
By incorporating vector commitments into tree structures, Verkle trees enable signature schemes and data authentication mechanisms that are both space-eficient and resistant to quantum attacks. This makes them a strong candidate for future cryptographic frameworks, especially in environments where memory, computation, and bandwidth are limited.
Vector commitments (VCs) allow committing to a sequence of values in such a way that individual elements can later be revealed and verified without disclosing the rest. This makes VCs particularly useful for privacy-preserving systems, cryptographic accumulators, authenticated databases, and other public verification schemes. One important challenge in this field is designing VCs that remain secure in the post-quantum era.
Recent research has explored how VCs can be constructed from lattice-based assumptions, especially the Short Integer Solution (SIS) problem. These lattice-based schemes support stateless updates, meaning proofs and commitments can be updated eficiently without requiring the full vector. Unlike traditional Merkle trees, where updating a single value may require recomputing many hashes, SIS-based constructions ofer better scalability.
However, early designs sufered from ineficiencies in large dimensions, as the cost for both the
committer and verifier scaled poorly [
The improved structure relies on specialized algebraic tools such as a “gadget” matrix and trapdoor sampling techniques. These components allow eficient preimage sampling and compact proof generation. Although the setup phase requires some trusted parameters and private initialization, the result is a VC system with small, verifiable proofs and support for stateless updates, all while being grounded in post-quantum security.
Overall, lattice-based VCs ofer a promising path toward scalable and quantum-resistant commitment schemes, making them valuable for advanced cryptographic protocols like Verkle tree-based digital signatures.
In signature schemes like the Merkle Signature Scheme (MSS), each one-time signature requires a unique key pair. For a tree of height , this results in 2 private keys, which becomes impractical to store in many real-world systems. To reduce this burden, a deterministic pseudo-random number generator (PRNG) can be used to generate keys on demand from a single initial seed. This approach eliminates the need to store all private keys. The PRNG takes an input seed ∈ {0, 1} and returns both a new seed and a pseudorandom output:
PRNG : in ↦→ (RAND, out).
Starting from a randomly chosen seed 0, a sequence of one-time signature seeds is derived iteratively: (11) (13) (OTS , +1) = PRNG( ), for = 0, 1, . . . , 2 − 1. (12) Each seed SOTSj is then used to deterministically generate the components of the -th one-time signature key:
(0, 1, . . . , −1 ) = PRNG (︀ OTS ︀) .
This method ensures that only the current seed is needed to compute the next key, significantly reducing memory requirements. Keys can be reconstructed exactly when needed-during signing or verification, without the need to store them persistently.
The same technique can be applied in Verkle trees, which also associate keys with leaf nodes. Each key-value pair can be generated dynamically using a seeded PRNG. This enables eficient signature generation and verification without the overhead of managing a large static key store.
To enhance security and randomness, the PRNG can be seeded using output from a Quantum Random Number Generator (QRNG). QRNGs use physical quantum phenomena to produce truly random bits, making them ideal for cryptographic applications. Seeding the PRNG with high-entropy quantum input ensures strong unpredictability in key generation, reinforcing the system’s resistance against quantum attacks. In practice, the PRNG is used in two phases: first, during key generation to initialize the tree structure, and second, at signature time to regenerate the specific one-time key needed. This method allows the system to remain lightweight and scalable while maintaining strong post-quantum security properties. As Verkle trees evolve, replacing classical commitment schemes with lattice- or hash-based post-quantum alternatives becomes critical to future-proofing such systems against quantum threats.
To ensure strong post-quantum security in our digital signature scheme, we adopt a SHAKE-based Deterministic Random Bit Generator (DRBG) as the core pseudorandom number generator. SHAKE functions, part of the SHA-3 family standardized by NIST (FIPS 202), ofer extendable output lengths and excellent resistance against both classical and quantum cryptanalytic attacks. This makes SHAKE-based DRBGs a natural choice for cryptographic applications in the post-quantum era. Unlike traditional DRBGs based on block ciphers, SHAKE-based DRBGs operate entirely through sponge construction. Given an initial seed with suficient entropy, the SHAKE function absorbs the seed into its internal state and then generates arbitrary-length pseudorandom output. This output is deterministic and indistinguishable from true randomness, provided the seed is unpredictable.
The advantages of SHAKE-based DRBGs include simplicity of design, strong resistance to diferential and linear cryptanalysis, and a reduced need for reseeding compared to block cipher-based generators. Their extendable-output nature allows for eficient key material expansion, nonce generation, and on-demand derivation of one-time keys without introducing unnecessary overhead.
In our architecture, the SHAKE-DRBG is seeded once with high-entropy input from a quantum random number generator (QRNG). From that point, the SHAKE function provides pseudorandom outputs used for generating key material and signature components. This hybrid setup ensures both unpredictability (due to QRNG) and determinism with performance eficiency (due to SHAKE). The use of SHAKE-based DRBG not only eliminates reliance on AES or counter-based mechanisms but also simplifies implementation in memory-constrained environments, making it especially suitable for post-quantum digital signature schemes deployed in IoT, embedded devices, or blockchain networks.
To support digital signature schemes in a post-quantum environment, we rely on a secure and eficient pseudorandom number generator (PRNG). For this purpose, we utilize a SHAKE-based DRBG (Deterministic Random Bit Generator), seeded with high-entropy input from a Quantum Random Number Generator (QRNG). This hybrid approach combines the cryptographic strength of the SHA-3 sponge construction with the unpredictability ofered by quantum phenomena. SHAKE-based DRBGs operate by absorbing a seed into the internal state of the sponge and then squeezing out arbitrary-length output. Unlike counter-based constructions that rely on block ciphers, SHAKE-based generators derive security from their cryptographic sponge design, eliminating the need for key or counter management. The seed is generated by a QRNG, ensuring high entropy and true randomness, which is critical for secure key generation in the quantum era.
Let the SHAKE-based DRBG be defined as follows: given an initial n-bit seed QRNGin from a QRNG, the generator produces a random output RAND of bits and an updated internal seed QRNGout of bits.
SHAKE-DRBG : {0, 1} → {0, 1} × {0, 1} ,
QRNGin ↦→ (RAND, QRNGout).
(14) The generation of one-time keys in the scheme begins with a uniformly random seed QRNG0. We then compute a sequence of derived seeds QRNG − OTS j for each in the range 0 ≤ < 2 , where defines the tree height. These seeds are recursively derived by applying the − function: (QRNG-OTS , QRNG+1) = SHAKE-DRBG( ), 0 ≤ < 2 .
(15) Each seed QRNG − OTS j then generates the corresponding one-time signature key , composed of blocks of -bit strings: (, QRNG-OTS ) = SHAKE-DRBG(QRNG-OTS ), = −1, . . . , 0. (16) Each invocation of CTRDRBG results in an update of the seed QRNG − OTS j, demonstrating that the signature key can be derived simply from QRNGj. Furthermore, the computation of QRNG − OTS j defines a new seed QRNGj+1 for the signature key ( + 1). The image below illustrates this process of generating a one-time signature key using CTRDRBG. This process starts with 0, the secret key, which has a length of . The seeds QRNGj+1 determined during the creation of the signature key subsequently replace 0.
This structure ensures that the entire one-time key is deterministically generated from a single seed. Furthermore, since each use of − updates the seed, it eliminates the risk of seed reuse. The updated seed QRNGj+1 becomes the basis for generating the next key Xj+1, ensuring that each signature key remains isolated and securely derived.
The process is visualized in Figure 2, where 0 initiates the secure generation chain. At each step, a new seed is derived and used to generate the next one-time signing key. Because SHAKE allows lfexible-length output, both the key and its expansion are eficiently supported without additional cryptographic primitives.
By seeding with quantum-generated entropy and leveraging the cryptographic properties of SHAKE, this key generation process achieves a high level of security and eficiency. The scheme guarantees that past keys cannot be reconstructed even if the current state is exposed, supporting forward security. Moreover, because SHAKE-DRBG is stateless and deterministic, no persistent state must be retained between key generations, reducing attack surfaces and simplifying implementation.
This method ensures that all one-time signatures generated before termination remain verifiable and secure. Since each signing key is used only once and is derived from a seed that cannot regenerate previous keys, the scheme maintains strong forward secrecy and post-quantum resistance.
To achieve both post-quantum security and implementation eficiency, we propose an improved Verkle signature scheme that combines a quantum random number generator (QRNG) with a SHAKE-based deterministic random bit generator (DRBG). This hybrid approach supports secure, on-demand key generation, minimizes persistent storage requirements, and is well-suited for real-world cryptographic systems operating under memory or processing constraints.
The design begins with a high-entropy seed generated using a QRNG. Quantum-generated randomness ensures unpredictability beyond the capabilities of classical pseudorandom sources. This seed is then used to initialize a SHAKE-based PRNG, selected for its post-quantum security assumptions, flexible output length, and eficient sponge function structure. The PRNG is employed in two critical stages: 1. Key Generation Phase – The SHAKE-based DRBG produces one-time signature key pairs deterministically from the initial seed. 2. Signing Phase – A fresh one-time signature key is derived for each message, ensuring signature uniqueness and forward secrecy.
By avoiding the need to store all keys and instead regenerating them from the seed, the system improves both scalability and security.
Let 0 be the initial -bit seed produced by the quantum random number generator. This seed initializes the SHAKE-based PRNG, which then outputs a sequence of one-time key pairs ( , ), where: • is the private signing key, • is the corresponding public verification key, • 0 ≤ < 2 , with ∈ N, ≥ 2 determining the tree height.
Each new key pair is generated on-demand and can be recomputed by replaying the PRNG from the original seed up to index , eliminating the need for persistent storage.
To sign a message , the following steps are executed: 1. Compute the message digest = ( ). 2. Use the next available one-time key (from the PRNG) to sign the digest. 3. Include the corresponding public key and the authentication path from to the Verkle tree root.
4. The final signature includes: sign = ( , , path, ).
This ensures that each signature is unique and cryptographically bound to a specific one-time key.
Verification involves: 1. Recomputing the message digest = ( ). 2. Verifying the one-time signature using . 3. Authenticating using the provided path in the Verkle tree. 4. Checking that the root commitment matches the known public key.
Only if all conditions are met is the signature accepted as valid.
Each one-time public key becomes a leaf in the Verkle tree. Internal nodes aggregate commitments using a vector commitment scheme. The root commitment of the tree acts as the global public key.
During signing: • The authentication path from leaf to the root is provided. • This allows the verifier to confirm ’s inclusion in the tree and link the signature to the public key.
This structure enables the system to store just one root public key while supporting a large number of one-time signatures.
This paper introduces an enhanced Verkle signature scheme that addresses the critical needs of modern cryptographic systems in a post-quantum era. The architecture integrates a SHAKE-based Deterministic Random Bit Generator (DRBG) with entropy sourced from a Quantum Random Number Generator (QRNG), providing a robust foundation for generating unpredictable and cryptographically secure keys. Our approach eliminates the dependency on large-scale key storage, a major drawback in traditional one-time signature schemes such as Merkle Signature Scheme (MSS), by allowing the deterministic reproduction of one-time keys on demand.
By employing Verkle trees, which ofer compact proofs and verification eficiency via vector commitments, the scheme drastically reduces the size of signatures and associated metadata. This is particularly beneficial in bandwidth-constrained or resource-limited environments, where large signature structures pose both computational and storage challenges.
The scheme also ensures: • Forward security: every key pair is used only once, preventing reuse and enabling strong resistance to key compromise. • Scalability: through stateless, on-the-fly key generation and tree-based verification, the architecture scales gracefully with the number of signatures and users. • Quantum resistance: SHAKE-based DRBGs belong to the SHA-3 family, which are known to resist attacks by quantum adversaries. Coupled with true quantum entropy via QRNG, this hybrid design strengthens both the unpredictability and long-term viability of the system. • Eficient verification and update paths: the use of vector commitments within Verkle trees supports batch verification and reduced overhead when validating multiple signatures, without sacrificing integrity or security.
This work was supported by the Shota Rustaveli National Science Foundation of Georgia (SRNSFG) N FR-24-15007. The author has not employed any Generative AI tools.