In recent years, work on quantum computers has made substantial progress. Many of the current public key cryptosystems can be broken if humans ever develop a powerful quantum computer. There are currently several commercial products that use these cryptosystems. Though we have developed defenses against quantum attacks, they are too risky and ineffective to be applied in daily life. The study analyzes hash-based digital signature methods. The evaluation of a digital signature using a Merkle tree. The paper investigates unique ideas using vector commitments and a Verkle tree. The authors of this study describe a novel, Verkle tree technology-based method for creating a digital signature system. This is accomplished using the Verkle tree, vector commitments, and vector commitments based on lattices for post-quantum aspects. This work also provides the theories behind post-quantum signature design using Verkle Tree.
Quantum computing will eventually prevail and spread more broadly. A cryptographic scheme for classical computers that can fend off attacks from quantum computers is known as post-quantum cryptography, also known as quantum encryption. Computers will be able to carry out complex calculations much more quickly than classical computers if they can take advantage of the special capabilities of quantum mechanics [1]. It should be obvious that a quantum computer might be able to perform some difficult tasks quickly. It is interesting to observe that a normal computer would need many years to accomplish these calculations.
Quantum computing will take over and become more prevalent when we get there. Most, if not all, currently in use conventional cryptosystems will likely be rendered useless by quantum computers. Particularly, systems based on the integer factorization problem (RSA). RSA-based cryptosystems are still widely employed in real-world applications; however, they are susceptible to assaults from quantum computers. The RSA cryptosystem is employed in a wide range of goods and programs. This cryptosystem is now used in an increasing number of commercial devices [2]. Because it is mostly utilized in encryption technologies, the RSA algorithm can be regarded as one of the most frequently used public key cryptosystems that develop with technology [3–7].
Many alternatives to RSA systems have been proposed, but none of them can be used in practice due to security or performance issues. One of the many proposed signature techniques is the hash-based one. Systems’ security depends on the hash function’s resistance to collisions because random integers are used as the initial random sequence [8]. It requires a lot of effort to create secure and efficient post-quantum cryptosystems and put them into use.
Many alternatives to RSA systems have been offered, but none of them can be utilized in practice due to security or performance difficulties. The hash-based signature method is one of many that have been suggested. The security of those systems depends on the hash function’s ability to withstand collisions because random numbers are utilized to generate the initial random sequences of those systems. Post-quantum cryptosystems need to be developed and put to use securely and effectively, which takes a lot of work [9–10]. Once quantum computing takes over, RSA and other asymmetric algorithms won’t be able to protect our personal information. We are working to develop post-quantum systems as a result.
In practice, quantum computer assaults can jeopardize traditional digital signature approaches. Our objective is to create RSA substitutes that are impervious to assaults from quantum computers. Digital signature systems based on hashes are one option. These apps employ the cryptographic hash function. Due to the low collision rates of the hash algorithms they use, these digital signature techniques are safe. The hash-based digital signature method is one RSA substitute. How safe these systems are is dependent on the cryptographic hash functions used.
We examined Merkle tree-based hashbased one-time signature methods. These post-quantum approaches can withstand quantum attacks. Verkle trees, a powerful update to Merkle trees that keep only the most important data, are more effective and enable more efficient verification methods. This reduces the amount of necessary storage space needed. We spoke about the implicit commitments of Verkle trees and vectors. Additionally, vector commitments based on lattices are taken into consideration about post-quantum features.
Quantum computers can easily break the present encryption schemes. Therefore, it is now conceivable for attacks made possible by quantum computers to be successful. The study [1] also covers one-way functions and one-time signature methods. Digital signature methods that can withstand assaults from quantum computers are presented in this article [2]. The work [8] includes information on the current state of cryptanalysis as well as the construction of the McEliece public-key encryption system with algorithmic and parameter options.
In [9], a variety of QRNG integration
techniques are offered. Scientists are
interested in quantum computers, according to
the article [10]. Cryptosystems based on the
integer factoring problem can be cracked by
quantum computers. It suggests that the RSA
system, one of the best-known public-key
cryptosystems, is vulnerable to attack by
quantum computers. The authors of
publications [11–15] discuss various quantum
number generators based on hash-based
digital signature techniques. The Merkle
scheme is fully explained in the article [
One-time signature schemes based on hashes have a lot of potential for the post-quantum era. Such is the operation of hash-based onetime signature techniques. First, key generation must be completed. The process of signing is then followed by the process of verifying the signature. The private key for the signature scheme is created using a secret key that is produced at random.
We concentrate on signature methods whose security is solely derived from the collision resistance of cryptographic hash functions. The Lamport-Diffie One-Time Signature (L-DOTS) scheme is an illustration of such a system [11]. It is assumed that computers have access to a constant supply of really random bits, which are effectively a series of impartial and independent coin tosses when constructing randomized algorithms and protocols. In actual applications, a sample that produces this sequence is obtained via a “source of randomness”.
To generate a Lamport-Diffie one-time signature key, 2n evaluations of the f function are required. The verification and signature keys are n-length, 2n-bit strings. During LDOTS {0,1}∗ signature creation document is signed using L-DOTS and signature key X. ( ) = = ( −1, … , 0) is the L-DOTS signature. the message digest for the message . ( −1[ −1], … , 1[ 1], 0[ 0]) {0,1}( , )
The n-bit strings of length n are used to create this signature. They are picked as message digest function d. The number of = is ( ( −1), … , ( 0)) = ( −1[ −1], … , 0[ 0]). long. generates signature, cryptographic functions that a processor can perform at a given time is usually calculated in hashes per second [13]. The ith bit string of this signature is xi[0] if the ith bit in d is 0, xi[1] otherwise. The signature does not require the evaluation of f. The signature is not dependent on the evaluation of f. The signature is n2 bytes
In the case of L-DOTS verification, the verifier ( − , … , ) if we want to verify ′ Consequently, whether it is or is not is decided: − , … ,
= ). message
digest the The Lamport-Diffie one-time signature’s security parameter n is an integer. A one-way function called ∶ {0,1}
→ {0,1} and a cryptographic hash function ∶ {0,1} → {0,1} are used by L-DOTS to construct an L-DOTS key pair [12]. By formula (1), the
= ( −1[0], −1[1], … , 1[0], 1[1], 0[0], 0[1]) {0,1}( ,2 )
= ( −1[0], −1[1], … , 1[0], 1[1], 0[0], 0[1]) {0,1}( ,2 )
The one-way function f, as defined by expression (3), is used to calculate the key: Hash-based one-time signature schemes involve key generation, signature creation, and verification. A secret key is generated at random to create the private key. The secret key and hash function are applied repeatedly to the message, resulting in the signature. The recipient verifies the signature using the same hash function and the received message. The signature is considered valid if the result matches the sent one.
Even though L-DOTS is big, it swiftly creates keys and signatures. The Winternitz One-Time Signature Scheme (W-OTS) is recommended as a way to reduce the number of signatures.
W-OTS lowers the number of signatures by signing many bits in a message digest with a single string that serves as the
One-time signature schemes are challenging due to the need for storing n digests, making them impractical for everyday use. The Merkle Tree, a solution, uses a binary tree as the root to replace multiple verification keys with a single public key.
Lamport or Winternitz signature scheme.
The customizable Merkle Signature Scheme (MSS) supports any cryptographic hash function and any one-time signature scheme.
Users are allowed to select the hash function and signature scheme that best meets their needs and security concerns thanks to this flexibility. We assume that ∶ {0,1}∗ → {0,1} is a cryptographic hash function. We also assume that the one-time signature scheme also completes the generating one-time signatures that give the necessary security features.
generating the
Merkle signature scheme key pair, the signer chooses ∈ ℕ, where ≥ 2. As a result, a key pair is created. It will be possible to sign and validate 2 papers as a result. It should be emphasized that this is very different from signature schemes like RSA, which allow the use of a single key pair to sign or validate numerous documents [14]. In actuality, however, this number is also limited by the methods employed to create the signature or by particular laws [15].
different key pairs ( , ), 0 ≤ < 2 . The verification key in this case is , and the signature key is . Merkle tree has the following leaves: ( ), 0 ≤ < 2 . A parent node is the hash value of the concatenation of its left and right offspring. This is how a Merkle tree calculates its internal nodes. The Merkle signature scheme public key serves as the
signature keys with a length of 2 make up the
computing 2 unique key pairs and evaluating a 2 +1 − 1 hash function.
One-time signing keys are successfully used by MSS to generate signatures. We must first calculate the n-bit
= ( ) to sign a message on M. Then, using the sth one-time signature key , ∈ {0, … , 2 − 1}, the signer creates a one-time signature, and verification key make up a Merkle signature.
The signer adds to the message the index s and the authentication path to the verification key ; to validate its authenticity. There are two steps in Merkle’s signature verification process.
The one-time the first stage to check the validity of d’s the validity of the one-time verification key .
A Merkle Tree with n nodes can be built in ( ) time because Merkle Trees are extremely quick. Unfortunately, their (log2 ) proof size is quite large and can be costly in terms of width. When a Merkle tree has many nodes, the resulting
massive. Our local storage may experience a large and costly strain as a result of the Merkle
Verkle trees are a powerful upgrade to Merkle
trees,
enabling
smaller
verifications
and
increased efficiency [
The Verkle Tree is a method to construct a
using
instead of cryptographic hash functions. To construct a tree, choose k pieces and compute a Verkle Tree using files f0, f1, ..., fn. Compute a Vector Commitment (VC) for each subset of files and determine if each membership proves PRi with relation to VC. Compute
In Fig. 2, 9 files with a branching factor of 3 are divided into subsets of size k = 3. Vector Commitment and membership proofs are computed over each subset, leaving obligations VC1, VC2, and VC3. Membership proofs PR9, PR10, and PR11 are computed for commitments VC1, VC2, and VC3 concerning commitment VC4. The Vector Commitment VC4 is computed over these commitments, with the root commitment being the digest of the Verkle Tree. The Merkle and Verkle trees have distinct characteristics for proofs. In a Merkle tree, all sister nodes must be considered, requiring proof that contains all nodes. However, the Verkle tree uses “batching nodes” to verify multiple pathways simultaneously, reducing the amount of evidence needed to establish a value. This makes the Verkle tree more efficient and faster than the Merkle tree in proving values.
Verkle trees require only the path and minimal additional information for proof, without sibling nodes. They benefit from a wider width, but Merkle Patricia trees do not. Wider trees lead to shorter routes, but the higher cost of proving every width -1 sister node per level is offset by the Verkle tree's lack of this cost.
A Verkle tree uses a unique hash algorithm, using vector commitments instead of conventional hashes, to compute an inner node from its offspring. This method is more efficient than Merkle trees, as they achieve the same goal but are smaller in size in bytes. The main difference lies in the use of vector commitments for cryptographic hash functions.
Fundamentals of cryptography called commitment schemes allow a value to be concealed and then revealed. Two essential traits of commitment systems are binding, which limits access to other values, and hiding, which reveals the bare minimum of the value's properties. The VC schemes enhance commitments to accommodate ordered value sequences. One goal of VC schemes is to enable commitment to a vector and then opening at any preferred indices binding, which makes it challenging to open relative to several values at the same time. This goal is combined with potential attribute concealing.
Users can commit to an ordered list of q
values, known as a vector, using VC The
commitment can be opened concerning
specific places in the future (for example, to
demonstrate that is the -th committed
message). Position bound requires vector
commitments, ensuring adversaries cannot
open commitments to two separate values
simultaneously. To achieve conciseness [
Security characteristics like hiding property may also be required for vector commitments. The commitment should keep the values and order of the vector’s components a secret. Contrarily, the hiding property does not play a significant role in the execution of vector commitments.
The ability to update VC is necessary. To update the commitment and the related openings, we have two algorithms. By switching the th message from to ′ and taking into account the modification of a commitment Com, the committer can acquire a (modified) Com’ holding the updated message. Holders of a message opening at position j concerning Com can use the second way to modify their evidence and make it valid concerning the new Com’.
Multiple methods are employed for committing to and verifying vector messages while taking into account our vector commitment system. The technique employs a message space M, a commitment space Com, and a proof space Pr, depending on the setup settings.
In essence, updating a commitment and proof should produce results that are comparable to those of generating a new commitment and proof on the altered message vector. Because state information is included in the results, numerous updates are possible within polynomial constraints.
To implement VC, we can make either the well-known RSA assumption or the Diffie
assumption.
In terms of the effectiveness of the resulting solutions, the “quality” of the underlying assumption, or both, vector commitment provides compact and
However, the resulting techniques must protect computers.
us from attacks
by Unfortunately, quantum quantum computers can currently defeat VC based on RSA. In this article, we strengthen earlier vector commitment and RSA assumptionbased schemes to increase their efficiency and security. We are developing Verkle tree-based signature systems, but we construct vector commitments using lattices. Our schemes are predicated on post-quantum assumptions.
The use of VC methods enables concisely committing to an ordered series of values, enabling the illustration of desired points in a condensed manner. Since VCs can be updated without knowing the complete vector, modifications to commitments and proofs are possible.
Cryptographic accumulators, external databases that have been verified, and cryptocurrencies are only a few SIS lattice problem, allowing for secure messages. The constructions are efficient and shorter than previous stateless updatable constructions, using private-key configuration and a central authority for public parameters.
Due to the committer and verifier parameters’ widths being quadratic and linear in the message dimension , respectively, in our prior construction’s
VC
scheme, the
construction is unsuited for large dimensions
in its current state. We provide an analysis of a
general -ary tree construction that, with no
increase in the sizes of the parameters or
commitments, converts a VC scheme for
dimension into one for dimension ℎfor any
desirable positive integer ℎ. The only sizes that
increase are the proof and proof-update sizes,
which grow linearly with ℎ but independently
of . The stateless updatability quality of the
basic
scheme
and
the
combinability
of
commitments and proofs, both of which are
crucial for distributed VCs, are not preserved
by this modification [
Here, we provide a customized tree-like transformation of our VC scheme built on SIS. Our transform, in contrast to the general one, keeps combinability and (differential) stateless updates because commitments are essentially linear in committed messages, though at the cost of slightly larger objects and a stronger SIS requirement. The transformation is based on the context’s core idea that was employed in a Merkle-tree-like structure based on SIS (which can be used as a VC).
In that case, the proof size ends up being proportional to ℎ log2 ( ℎ) since a proof must contain all of the brother-node information for each step in a root-to-leaf path. (The length of the proofs along the path and the sizes of the integers inside of them are the sources of the llog2( ℎ) factor.) The same general principle holds true for our SIS-based VC scheme, with the added benefit that proofs need not include sibling information, meaning that the proof increases simply as ℎlog2 ( ℎ) = size ℎ3log2 .
For any choice of magnitude and tree height ℎ, our design is quantitatively a strict improvement (although at the cost of private setup).
Additionally, according to its performance profile, using a moderately large
and a correspondingly smaller ℎ can ultimately produce an asymptotic proof size that is equivalent to that of the generic tree transformation for VCs while maintaining combinability and stateless updates (though at the cost of private setup and a stronger SIS assumption).
Our constructs employ conventional methods for preimage sampling and SIS— based trapdoors. The “gadget” matrix, abbreviated G, is used in the constructions This matrix has an integer dimension of n by w. In building the trapdoor, the matrix G is essential. G illustrated by the formula: G = I ⊗ (1, 2, … , 2⌈log2 ⌉−1), where I is the n×n identity matrix, and ⊗ stands for the Kronecker product. This illustration serves as a model, although any acceptable matrix G with certain characteristics may be utilized. Deterministic function G−1: ℤ → ℤ is an inversion operation with particular characteristics. The formula G ⋅ G−1(u) = u for small values of , and the norm of G−1(u) is constrained by for all u in ℤ .
G is a matrix with n×w dimensions and
values . When performing the G−1operation
(computing the inverse of G), the magnitude
bound G for the gadget matrix G is employed.
Vectors for messages are chosen from a set ̅.
̅ is a collection of w-dimensional vectors,
where each element is drawn from a subset of
‾. ‾ is a subset of the integers and is defined by
the values— and . The chosen integer, ℎ
The chosen integer. We employ algorithms that
were constructed for previous construction
[
The following algorithms have been defined.
Setup Algorithm:
The S̅̅e̅̅t̅u̅̅p̅ℎ algorithm generates outputs based on input parameters. A commitment parameter , a matrix U (made up of multiple submatrices), and vp are included in outputs.
U(1) is the same as the matrix U that was discussed earlier. The matrix S(1) is an identity matrix of size wd×wd.
For each k from 1 to h: S( ) = I ⊗ G−1(U( −1)) ∈ ℤ × U( ) = US( ) ∈ ℤ × (5) (6)
The inverse of G and the matrix U( −1)are used in an operation to produce S( ). The matrix U( −1) is multiplied by S( ) to get U( ). Each of the blocks that make up U( ) can be calculated separately using U and a value ‾ (‾ ∈ [ ]) without having to calculate the complete matrix.
Commit Algorithm: From 1 to h, for each k:
The C̅̅o̅̅m̅̅̅m̅̅i̅t̅ algorithm requires a commitment parameter cp and a message vector m̅. Applying the inverse of G on U( ) results in the computation of the value c̅ . Outputs include c̅ and ̅ .
Open Algorithm:
For k = 1, the ̅O̅̅p̅̅e̅n̅̅1algorithm is the same as the “Open” operation.
For each k from 2 to h: • Based on the given values and the value ‾′, a value ‾ is calculated. • Subvectors are created from a message vector m̅. • The Open algorithm and specific inputs are used to determine the p value. • Using the Commit algorithm from the prior phase, a commitment value (c̅ ,−) is generated. • Using specific inputs and the Open algorithm, a value ‾′‾′ is produced. • The result is ‾ ‾.
Using the Verify operation, the ̅V̅e̅̅r̅i̅f̅y̅1 algorithm verifies some inputs for k = 1.
For each k from 2 to h: • An index and a value ‾′ are defined based on ‾. The components of the ‾ ‾ value is separated into components. The process is rejected if a few verification requirements are not satisfied. • The process is denied if the verification from the (k–1)th algorithm— ̅V̅e̅̅r̅i̅f̅y̅ −1 fails. If not, it’s accepted.
Update Algorithms—From the linearity of commitment operations, update algorithms can be inferred.
Implementing one-time signature methods can be challenging because a different key pair must be used to sign every message. These systems’ drawback is that n digests must be saved, which makes them impractical for routine use. Therefore, regardless of the number of files we have, we would require a method that allows us to save a uniform-sized digest. The Merkle tree was suggested as a solution to this issue. This method can replace numerous verification keys with a single public key by employing a binary tree as the root [30–
Merkle trees are quickly computed; it takes ( ) time to build a Merkle tree with n nodes. A Merkle tree with several nodes can be used to generate large Merkle proofs. Unfortunately, the size of their (log2 ) proof is extremely huge and can be expensive. The Merkle proof alone might be a heavy and costly burden on our local storage. To sign 2n messages, the tree must be n heights tall. The size of their proofs, ( log ), is more than that of Merkle Trees when using wider-width trees (w-ary trees). The proof size is fixed at (1), when a vector commitment method is used, however, the building extremely validation and signing of 2 papers. The signer will generate 2 distinct key pairs ( , ), 0 ≤ < 2 . In this case, the verification key is and the signature key is . Both of them are bit strings. The leaves of the Verkle tree are ( ), 0 ≤ < 2 . Each node is a hash value that is formed by concatenating the hashes of its offspring, and they are calculated and used as the tree’s leaves. The public key is the primary commitment in the
Verkle cryptography system. To create a public key, 2 pairs of keys must be calculated [34].
One-time signature key generation allows us to create signatures. To sign a message on M, the n-bit = ( ) must first be calculated. An arbitrary size message of size m is first changed into a message of size n using the hash function. The document’s signature is made up of the root commitment, one-time signature, one-time verification key, and finally, indexes for the evidence [35–36].
The one-time signature of should be authenticated using according to how Verkle’s signature verification works. The VCi commitments are confirmed if this is the case.
The paper gave a thorough overview of cryptography methods that might be used in both traditional and quantum settings. We covered post-quantum cryptography systems.
We discussed hash-based one-way functions, as well as how we can integrate them into strong defense against quantum assaults even though the verification size is too big. Each child in a Merkle tree is represented by the hash of the parent node.
Our revised Verkle tree model defines a parent node as the vector commitment of its children. To implement the new technology, we discussed vector commitment
and commitments based on hard lattice issues. The Verkle system allows for substantially smaller verifications, which is a
significant improvement over the Merkle scheme. Instead of showing all nodes at each level, verification only needs one proof to authenticate all parent-descendant relationships, namely all [5] A. Bessalov, et al., Modeling CSIKE commits from each leaf node to the root. This Algorithm on Non-Cyclic Edwards makes it possible to reduce the verification size Curves, in: Workshop on Cybersecurity by around 6–8 times when compared to the Providing in Information and conventional Merkle method. Telecommunication Systems, vol. 3288
In our revised method, a Verkle tree was (2022) 1–10. therefore taken into consideration instead of a [6] A. Bessalov, et al., Multifunctional CRS Merkle tree. In this case, vector commitment is Encryption Scheme on Isogenies of Nonsufficient to establish the proof. Based on the Supersingular Edwards Curves, in: premise of the lattice, we used vector Workshop on Classic, Quantum, and commitments to build the Verkle tree. Post-Quantum Cryptography, vol. 3504
We must ensure that the strategies that (2023) 12–25. emerge safeguard us against attacks from [7] A. Bessalov, et al., Computing of Odd quantum computers. Our earlier vector Degree Isogenies on Supersingular commitments based on RSA could be Twisted Edwards Curves, in: Workshop compromised by quantum computers. The on Cybersecurity Providing in strategy has since been improved to make it Information and Telecommunication safer and more effective. Verkle trees are used Systems, vol. 2923 (2021) 1–11. in our signature procedures, whereas lattices [8] B. Bhaskar, N. Sendrier. McEliece are used to create vector commitments. We use Cryptosystem Implementation: Theory post-quantum assumptions to underpin our and Practice, Post-Quantum systems. Cryptography, (2008) 47–62. doi: 10.1007/978-3-540-88403-3_4. 10. Acknowledgment [9] I. Maksim, et al,. Advantages and Challenges of QRNG Integration into This work was supported by Shota Rustaveli Merkle, Sci. Practical Cyber Secur. J. 4(1) National Science Foundation of Georgia (2020) 93–102. (SRNSF) STEM-22-1076. [10] A. Gagnidze, M. Iavich, G. Iashvili, Novel Version of Merkle Cryptosystem, Bulletin of the Georgian National References Academy of Sciences 11(4) (2017). [11] L. Lamport, Constructing Digital [1] J. Buchmann, E. Dahmen, M. Szydlo, Signatures From a One Way Function Hash-based Digital Signature Schemes, (1979).
Post-Quantum Cryptography, Springer, [12] M. Iavich, et al., Post-Quantum Digital (2009) 35–93. doi: 10.1007/978-3-540- Signatures with Attenuated Pulse 88702-7_3. Generator, in: Information Society and [2] L. Chen, et al, Report on Post-Quantum University Studies vol. 2698 (2020) 42– Cryptography, National Institute of 45.
Standards and Technology 12 (2016). [13] M. Iavich, et al., Improvement of Merkle doi: 10.6028/nist.ir.8105. Signature Scheme by Means of Optical [3] A. Bessalov, et al., Implementation of the Quantum Random Number Generators, CSIDH Algorithm Model on Advances in Intelligent Systems and Supersingular Twisted and Quadratic Computing (2021) 478–487. Edwards Curves, in: Workshop on [14] M. Iavich, A. Gagnidze, G. Iashvili, Hash Cybersecurity Providing in Information Based Digital Signature Scheme with and Telecommunication Systems, vol. Integrated TRNG, CEUR Workshop 3187, no. 1 (2022) 302–309. Proceedings vol. 2145 (2018) 79–82. [4] A. Bessalov, et al., CSIKE-ENC Combined [15] A. Hülsing, J. Rijneveld, F. Song, Encryption Scheme with Optimized Mitigating Multi-Target Attacks in HashDegrees of Isogeny Distribution, in: Based Signatures, Public-Key Workshop on Cybersecurity Providing in Cryptography—PKC 2016 (2016) 387– Information and Telecommunication 416. doi: 10.1007/978-3-662-49384Systems, vol. 3421 (2023) 36–45. 7_15.