The paper investigates the vulnerability of classical digital signatures, particularly RSA, in the face of advancing quantum computing. Shor's algorithm, which is capable of efficiently factoring large numbers on a quantum computer, poses a significant threat to traditional public-key cryptography. Therefore, the paper explores post-quantum digital signature schemes based on hashing, which are known for their resilience to quantum attacks. A key focus is the introduction and application of the Verkle Tree, a novel data structure, in the design of digital signatures. Our methodology, which uses Verkle Tree enhances security and efficiency in the post-quantum era, offering a practical methodology to counter quantum threats. The paper also offers post-quantum design concepts leveraging the Verkle Tree, offering the possibility of its integration into broader cryptographic protocols. In conclusion, the paper contributes to the discussion on the future of digital signatures by addressing classical vulnerabilities, introducing postquantum alternatives, and proposing innovative design concepts with the Verkle Tree. This work illustrates the importance of quantum-resistant cryptographic solutions and provides practical and theoretical approaches for secure digital signatures in the post-quantum landscape.
Recently, the leading engineers and scientists of the world
are working on the creation of quantum computers.
Recognized leaders in the development of quantum
computers, the Google Corporation, the Association of
DWAVE and Space Research Universities, and the federal
agency NASA are already ready to make a breakthrough in
the field of quantum technologies. In October 2019, Google
announced the achievement of quantum supremacy, which
caused serious dispute, but given that the technological
giants are in a hurry to create the first quantum computers
and have made significant progress in this direction, the
world may be approaching the beginning of a new era.
Google claims that the new design of the chip can increase
memory productivity ten times, from 100 to 1000 qubits.
IBM is next as it declares that by the end of 2023, it will
create a quantum processor with a capacity of more than
1000 qubits with about 50 logical qubits. It has already
introduced a processor with 127 cubits in 2021 and a
433cube processor in 2022. Chinese scientists also claim that
“Zuchongzhi 2”—a 66-qubit quantum processor, completed
the task 1 million times faster than the Google processor.
This processor was developed by the research group of the
Center for Achievements in Quantum Information and
Quantum Physics of the Chinese Academy of Sciences
together with the Shanghai Institute of Technical Physics
and the Shanghai Institute of Microsystems and Information
Technologies [
The Daytime RSA cryptosystem is used almost everywhere, it is used by many large organizations such as government agencies, corporations, banks, government, and not only laboratories and universities. In addition, RSA is used in commercial products, hardware, operating systems, Ethernet, network smart and cards, and also in cryptographic equipment. With a total of about 500 million users, the RSA is one of the most widely used public key cryptosystems. So hacking RSA can lead to complete chaos. Today’s challenge is to create alternatives to RSA that can withstand the attacks of quantum computers. As an alternative to RSA, digital signature hashing schemes based on a cryptographic hash function can be considered. The security of this signature is based on the collision resistance of the hash function.
0000-0002-3109-7971 (M. Iavich) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Digital signatures rely on asymmetric cryptography, which
involves a pair of keys: a private key for signing and a public
key for verification. The mathematical foundation often
involves algorithms like RSA, DSA, or ECDSA. The private
key creates the signature, and the public key verifies it [
Hashing: 1. 2.
Before signing, the document or message is usually hashed. A hash function condenses the data into a fixed-size string of characters. The hash ensures that even a slight change in the document will result in a vastly different hash value.
The hash is then encrypted with the sender’s private key to create the digital signature. The private key ensures that only the sender could have created this specific signature.
The recipient hashes the received document using the same hash function used by the sender.
The decrypted hash is compared with the hash of the received document.
If the two hashes match, it confirms that the document has not been altered, and the signature is valid.
Non-Repudiation: Digital signatures provide nonrepudiation, meaning the sender cannot deny their involvement or the authenticity of the signed document. This is because only the sender possesses the private key needed to generate that specific signature.
Key Management: The security of digital signatures relies heavily on proper key management. Safeguarding private keys is crucial to prevent unauthorized access and potential forgery. Key generation, storage, and distribution should follow secure practices.
Time Stamping: To address the issue of the validity period of digital signatures, timestamping services are often used. They provide proof that the signature existed at a particular time, adding another layer of security and trust.
Use Cases: Digital signatures find applications in various fields, such as:
Document Authentication: Ensuring the integrity and authenticity of digital documents.
Financial Transactions: Verifying the origin and integrity of financial transactions.
Software Distribution: Ensuring that software has not been tampered with during distribution.
Legal Contracts: Providing a digital equivalent to handwritten signatures in legal documents.
Challenges: Despite their effectiveness, digital signatures face challenges like evolving cryptographic standards, quantum computing threats, and the need for widespread adoption to achieve their full potential.
RSA, named after its inventors Ron Rivest, Adi Shamir, and
Leonard Adleman, serves as a foundational public-key
cryptosystem widely employed for digital signatures. At its
core, RSA involves a pair of keys—a public key and a private
key. The public key, comprising a modulus (n) and an
exponent (e), is openly shared, while the private key,
including(n) and another exponent (d), remains
confidential. The system’s security hinges on the intricate
challenge of factoring large prime numbers, forming the
basis of its strength [
In the generation of digital signatures using RSA, a
meticulous process unfolds. Before signing, the document
undergoes hashing, typically utilizing a secure hash
function like SHA-256. This hashed value is then padded, an
important step in ensuring a consistent size and mitigating
specific vulnerabilities, often employing schemes such as
PKCS#1 v1.5 or PSS. Subsequently, the padded hash is
encrypted using the sender’s private key, resulting in the
creation of the digital signature [
On the recipient’s end, the process of verifying the digital signature unfolds. The received document is hashed, mirroring the same hash function employed by the sender. Simultaneously, the recipient decrypts the digital signature using the sender’s public key. Successful matching between the decrypted signature and the hash value validates the signature, assuring the document’s integrity and authenticity.
The strength of RSA-based digital signatures is based on their security features. The complexity of factoring large numbers contributes to robust security. The choice of key length plays a pivotal role, with longer keys offering heightened security albeit potentially demanding more computational resources. Despite RSA’s general slowness compared to symmetric-key algorithms, its computational cost for digital signatures is typically deemed acceptable. Careful consideration of padding schemes, such as PKCS#1 v1.5 and PSS, is essential to fortify security against potential vulnerabilities.
In practical applications, RSA-based digital signatures find extensive use. They authenticate the source of messages in secure communication protocols like SSL/TLS, ensure the authenticity and integrity of digitally signed documents, and play a crucial role in the generation of digital certificates.
However, challenges persist. The need for longer key lengths to thwart evolving threats and the looming potential of quantum computers pose considerations. Additionally, the computational overhead of RSA, especially in resourceconstrained environments, remains an ongoing concern.
RSA-based digital signatures continue to be usable in classical cryptography, offering a reliable means to ensure the authenticity and integrity of digital information. Ongoing research is essential to address emerging challenges and enhance the security of RSA-based systems as technology evolves.
RSA, as a widely used public-key cryptosystem, is vulnerable to attacks by quantum computers due to its reliance on the difficulty of factoring large numbers. Quantum computers, with their potential to perform certain calculations exponentially faster than classical computers, pose a significant threat to traditional cryptographic algorithms.
The most notable algorithm for factoring large numbers efficiently on a quantum computer is Shor’s algorithm. Shor’s algorithm can factorize large numbers in polynomial time, rendering the security assumptions of RSA obsolete. As a result, the security of RSA and other widely used public-key cryptography systems, such as ECC (Elliptic Curve Cryptography), is compromised in the era of quantum computing.
To address the threat posed by quantum computers, the cryptographic community is actively exploring and developing quantum-resistant or post-quantum cryptographic algorithms. These algorithms aim to maintain security even in the face of quantum attacks. Some proposed post-quantum alternatives include lattice-based cryptography, hash-based cryptography, code-based cryptography, and multivariate polynomial cryptography.
Transitioning from RSA to quantum-resistant algorithms is crucial for maintaining the security of digital signatures and other cryptographic applications in the postquantum era. Organizations and researchers are working collaboratively to standardize new cryptographic algorithms that can withstand quantum attacks.
In the context of digital signatures, the move to quantum-resistant algorithms ensures that the integrity and authenticity of signed documents remain secure even as quantum computing capabilities advance. While RSA has been a workhorse for secure communication and digital signatures, the ongoing development and adoption of quantum-resistant algorithms are essential for preparing for the future landscape of quantum computing threats.
Elliptic Curve Cryptography (ECC) digital signatures are at the forefront of modern public-key cryptography, striking a delicate balance between stringent security requirements and computational efficiency.
ECC leverages the intricate properties of elliptic curves
over finite fields to facilitate cryptographic operations
effectively. During the key generation phase, ECC entails
the creation of a key pair comprising a private key and its
corresponding public key. The private key, selected at
random, serves as the cornerstone for deriving the public
key through elliptic curve computations [
To generate an ECC digital signature, the message undergoes hashing using a cryptographic hash function, resulting in a fixed-size hash value. A critical aspect involves the generation of a random nonce to thwart signature predictability.
Subsequently, the ECDSA algorithm computes a pair of values, typically represented as (r, s), constituting the digital signature associated with the hashed message. Verification of an ECC digital signature necessitates hashing the received message and reconstructing a point on the elliptic curve using the public key and elliptic curve operations. The computed point, combined with the received signature, undergoes mathematical scrutiny to validate its authenticity.
Successful verification establishes the genuineness and integrity of the message. ECC’s robust security is achieved through shorter key lengths in comparison to conventional algorithms, rendering it computationally efficient. As a versatile cryptographic tool, ECC digital signatures find utility in various domains such as secure communication protocols, authentication mechanisms, and digital certificates.
With its resilience against quantum attacks, ECC serves as a cornerstone in the continual advancement of cryptographic solutions. Quantum computers pose a potential threat to certain public-key cryptography algorithms, including Elliptic Curve Cryptography (ECC), which underpins ECC digital signatures.
The primary quantum algorithm posing a threat to ECC is Shor’s algorithm. Shor’s algorithm proficiently factors large numbers and computes discrete logarithms, which are foundational challenges for breaking RSA and ECC, respectively.
Hash-based digital signature schemes are a class of cryptographic algorithms that rely on the properties of hash functions to achieve secure and efficient digital signatures. These schemes are particularly interesting in the context of post-quantum cryptography due to their resilience against quantum attacks, especially when other traditional publickey cryptosystems like RSA or ECC may become vulnerable.
Lamport-Diffie’s hash-based one-time signature scheme is regarded as a promising and resilient alternative for the post-quantum era, presenting a paradigm shift in cryptographic methodologies to address the vulnerabilities posed by quantum computing advancements. This scheme stands out as a beacon of security in an environment where traditional cryptographic systems, especially those reliant on integer factorization, face the imminent threat of compromise through quantum algorithms such as Shor’s algorithm. With its foundation in hash functions, LamportDiffie introduces a robust and quantum-resistant approach to digital signatures, offering cryptographic practitioners and researchers an avenue to fortify information security in concatenation of all branches related to “authi” concerning
We can tell, that Verkle trees are an improved version of
upgraded Merkle trees, their construction is very similar to
that of Patricia’s Merkle tree [
Fig. 1 shows a Verkle tree of 9 files with a branching rate of 3. First, the files are split into subsets of size k = 3, at the next step, a commitment vector and corresponding membership proofs are calculated for each subset. After dividing the files into subsets of size k = 3, by calculating vector commitments and membership proofs for each subset, we obtain commitments , and . As for the
commitment vector, which is computed with these last three commitments together with the , and membership proofs for the , accordingly, concerning the and
commitments, commitment. The final resolution of the Verkle tree is the root commit, in this case
The proof in a Merkle tree must contain every flattened node in the tree that shares a common ancestor with any node on the path leading to the proof node.
For this reason, the size of the signature is very large. Flattern nodes must be provided at each level since the entire set of child nodes is needed to calculate the value of a node, and this continues until the root of the tree is reached. larger tree has a shorter path in both Merkle and Verkle’s cases, but in a Merkle Patricia tree this effect runs down by the high cost of having to provide full-width 1 flatter node per proof branch.
Scheme Merkle Tree Merkle Tree (w-ary) Vector Commitment Verkle Tree Construction ( ) ( ) ( ) (w )
Update (log )
Proof Size (log ) ( log ) ( log ) ( )
(1) ( log ) (log ) Verkle’s core commitment is a public key (Fig. 2). ||proof, root commit) Verkle is done as follows, one-time signature sig must be verified with , if found correct, all checks are calculated using “authi,” index arb and . The signature is verified If the tree root matches the commitment one.
The vector commitment must be chosen specifically, it must be resistant to the attacks of quantum computers. In the case of vector commitment is quantum resistant the final digital signature is also quantum resistant.
The Verkle scheme indeed represents a significant advancement over the traditional
Merkle scheme, introducing key enhancements that contribute to both efficiency and scalability in cryptographic applications. By allowing the use of smaller keys and optimizing the verification process, the Verkle scheme showcases its potential as a powerful upgrade. (4) One notable feature is the reduction in the amount of verification required, approximately by a factor of 6-8, compared to the Merkle scheme. This optimization is achieved by streamlining the verification process through a single proof that validates all parent-child connections, from leaf nodes to the root. This innovation not only enhances efficiency but also paves the way for increased scalability, addressing crucial concerns in contemporary cryptographic systems.
While the Verkle scheme introduces a more complex cryptographic framework, the benefits it brings in terms of reduced verification overhead and improved scalability make it a compelling choice for applications where these factors are paramount. The utilization of SNARKs (Succinct Non-Interactive Arguments of Knowledge) for Verkle proof verification further aligns with the trend of leveraging advanced cryptographic tools for enhanced efficiency.
Looking ahead, the inevitability of quantum computing advancements necessitates a strategic shift towards STARKs (Scalable Transparent Arguments of Knowledge) proofs with hashes. This shift is driven by the recognition that the linear homomorphisms on which Verkle trees depend may no longer be secure in the face of quantum computing capabilities. While this transition introduces challenges, it also opens avenues for exploring alternative cryptographic primitives that align with postquantum assumptions.
Moreover, the mention of SNARK-based Verkle proof verification and the potential for reverting to SNARK Merkle proofs when improved underscore the adaptability of cryptographic schemes in response to evolving technologies. This adaptability becomes crucial in ensuring the long-term security and efficiency of cryptographic systems.
In summary, the Verkle scheme represents a significant leap forward in cryptographic design, offering tangible benefits in terms of reduced verification complexity and enhanced scalability. As quantum computing looms on the horizon, the transition to STARKed proofs reflects a proactive stance in preparing cryptographic systems for the challenges posed by evolving technologies. This adaptability, coupled with ongoing advancements in cryptographic tools, positions the field for continued innovation and the development of schemes grounded in post-quantum assumptions, ensuring the robustness of cryptographic protocols in the face of emerging threats.
This work was supported by Shota Rustaveli National Science Foundation of Georgia (SRNSF) [STEM–22-1076].