- The critical analysis of the existing hash based digital signature schemes and their improvements is done in the article. One of the improvements is integrating PRNG to Merkle crypto system. It is shown that integrating PRNG to Merke is not safe, because quantum computers are able to break PRNGs, that were considered safe against attacks implemented on classical computers.
TRNG based on qubits behavior is offered in the article and is offered to integrate this TRNG to Merkle. By means of the size of the signature key is reduced.
The principle of the crypto system is not changed, but only TRNG is integrated. TRNG is completely safe; it is based on the state of qubits, which are real random numbers. So the received scheme is secure.
Scientists and cyber security experts are actively working on the development of quantum computers.
Google Corporation, Universities Space Research Association and federal agency NASA together with DWAVE, the manufacturer of quantum processors began to work on creation of quantum processors. D-Wave 2X is a quantum processor that contains 2,048 physical qubits. Usually 1152 qubits are used to perform calculations.
Google is working on releasing the new CPU. Twenty qubit processor is already undergoing tests, and the company promises to have its working forty nine qubit chip ready by the end of this year. Until it began trialing the twenty qubit chip, Google’s most powerful quantum chip was the nine qubit effort from 2015. Each additional qubit doubles the data search area, so the calculation speed is significantly
Quantum computers will be able to break most, if not absolutely all conventional cryptosystems, that are widely used in practice.
So, traditional digital signature systems that are used
presently in practice are vulnerable to attacks implemented on
quantum computers. The security of these systems is based on
Copyright held by the author(s).
the problem of factoring large numbers and calculating
discrete logarithms. Some cryptosystems for example RSA
system with four thousand bit keys are considered useful to
protect information from attacks implemented on classical
computer, but are absolutely not protected against attacks
implemented using quantum computers [
RSA cryptosystem is used in many products on different platforms and in different areas. To date, this cryptosystem is integrated into many commercial products, the number of which is growing every day. RSA system is also widely used in operating systems from Microsoft, Apple, Sun, and Novell. In hardware performance RSA algorithm is used in secure phones, Ethernet, network cards, smart cards, and is also widely used in the cryptographic hardware. Along with this, the algorithm is a part of the underlying protocols protected Internet communications, including S / MIME, SSL and S / WAN, and is also used in many organizations, for example, government, banks, most corporations, public laboratories and universities.
RSA BSAFE encryption technology is used approximately by 500 million users worldwide. Since in encryption technology is mostly used the RSA algorithm, it can be considered one of the most common public key cryptosystems being developed together with the development of the Internet.
On this basis the RSA destruction will entail easy hacking of most products that can grow into a complete chaos
Active work is being conducted to create RSA alternatives, which are protected from attacks by a quantum computer.
Hash based digital signature schemes are considered as
one of the RSA alternatives. These schemes use a
cryptographic hash function. The security of these digital
signature schemes relies on the collision resistance of the hash
functions that they use [
The signature key X of this system consists of 2n lines of length n, and the lines are selected randomly.
X= (xn-1[0], xn-1[
Y= (yn-1[0], yn-1[
Message m of arbitrary size, is transformed into size n by
means of the hash function:
h(m)=hash = (hashn-1, … , hash0) (4)
Function h is a cryptographic hash function:
h: {0,1} *{0,1} n
Signature occurs as follows:
sig= (xn-1[hash n-1], …, x0[hash0]) ∈ {0,1} n,n (5)
If the i-th bit in the message is equal to 0, i-th string in this
signature is assigned to xi[0]. If the i-th bit in the message
is equal to 1, i-th string in this signature is assigned to xi [
For signature verification sig = (sign-1, …, sig0), the hash of the message is calculated. hash = (hashn-1, … , hash0) and the following equality must be verified: (f(sign-1), …, f(sig0)) = (yn-1[hashn-1], …, y0[hash0]) (6) If it is true, then the signature is correct.
In Lamport one-time signature scheme, key generation and
signature generation are quite effective, the size of the
signature is very large as it is equal to n2. Winternitz one-time
signature scheme was proposed in order to decrease the
signature size. In Winternitz one-time signature scheme
several bits of the hashed message are signed simultaneously
with one string of the key, so the length of the signature is
reduced significantly [
The signature key X of this system consists of sn lines of length n, and the lines are selected randomly.
Winternitz parameter is selected w> = 2, it must be equal to the number of bits to be signed simultaneously. s1=n/w and s2=(log2s1 +1+w)/w are calculated (7) s= s1+ s2 (8) X= (xs-1[0], …, x0) ∈ {0,1} n,s (9)
Y= (ys-1[0], …, y0) ∈ {0,1} n,s, where (10) yi=f2^w-1(xi), 0<=i<=s-1 (11) The verification key and the signature are equal to ns bits.
To sign the document, message must be hashed hash=h(m) If length of hash is not devisable by w minimum number of zeros are prepended to hash and it is divided into s1 parts of length w. hash=ks-1,…, ks-s1 (12) the checksum is calculated: с=∑i=s-s1s-1(2w-ki) (13) as c<= s12w, the length of its binary representation is log2 s12w+1 (14) If the length of representation is not devisable by w, the minimum number of zeros must be prepended to this binary representation and must be divided into s2 parts of length w. с=ks2-1,…, k0 (15) Finally, the signature of m is calculated: sig=(f^ks-1(xs-1), …, f^k0(x0)) (16) The size of the signature is sn.
bit strings ks-1,…, k0 are calculated to verify the signature sig = (sign-1, …, sig0) (17) The following equality is checked: (f^(2w-1-ks-1))(sign-1), …, (f^(2w-1-k0))(sig0) = yn-1, … y0 (18) If the signature is correct, then sigi =f^ki(xi) (19) (f^(2w-1-ki))(sigi)= (f^(2w-1))(xi)=yi ; i=s-1,…, 0 (20) The size of the signature in Winternitz one-time signature scheme is significantly reduced ns<n2, so the length of the key is significantly reduced, because: ns<n2<2n2
II. MERKLE CRYPTO-SYSTEM To sign the message using one-time signature scheme, different key pair must be used for every message. This is very problematic, because it is very difficult to exchange big number of keys.
Merkle digital signature scheme is the solution for this
problem. The scheme uses a binary tree in order to replace a
large number of verification keys with one public key, that is
the root of this tree [
Message m of arbitrary size, is transformed into size n by means of the hash function. h (m) = hash, and is generated a one-time signature using arbitrary one-time key Xarb, the document's signature will be the concatenation of: one-time signature, one-time verification key Yarb, index arb and all fraternal nodes authi in relation to Yarb. Signature= (sig||arb|| Yarb||auth0,…,authH-1) (22)
To verify the signature, the one-time signature of sig is verified using Yarb, if it is true, all the nodes a [i, j] are calculated using “authi”, index arb and Yarb. Finally, the root of the tree is compared with public key, if they are equal, then the signature is correct.
2H pairs of one-time keys must be calculated in order to generate the public key. Storing such a big number of key is problematic in practice.
To save the space, it was suggested to use the PRNG random
number generator in Merkle signature scheme [
PRNG : {0, 1}n: {0, 1}n x {0, 1}n
The seed seed0 of length n is chosen randomly, using seedi is generated otsi, as following: PRNG(seedi) = (otsi , seedi+1) 0 ≤ i <2H (23) otsi is changed each time when PRNG launches. For Xi key calculation only seedi must be known.
Signature and verification are performed in the same way as in the standard version of Merkle crypto system.
Quantum computers are able to break PRNG-s, that were considered safe against attacks implemented on classical computers. PRNG Blum-Micali turned out to be vulnerable to polynomial quantum time attack. This PRNG is considered safe from attacks implemented on standard computers. This attack uses Grover algorithm along with the quantum discrete logarithm, and can restore the values at the generator output for this attack.
These type of attacks represent a threat of cracking PRNGs, that are used in many real-world crypto systems. Merkle crypto system with built-in PRNG can be vulnerable to attacks implemented on quantum computers. We suggest using a true random number generator based on qubits, TRNG.
To construct this TRNG states and qubits must be considered.
Information in a quantum computer is encoded in quantum
bits or qubits. Like a bit, the qubit allows two eigenstates
(conditionally | 0> and | 1>), but unlike the bit, the qubit
admits a superposition of these states, which means that it is
more "informative" [
In a system with one qubit, the quantum state of a qubit is denoted by: α|0>+β |1> where α and β are complex numbers; |α|2+ |β|2=1 (24) |0> - is the ground state of qubit |1>- is the excited state of qubit This qubit is in the state |0> with probability α2 and is in a state |1> with probability β2.
When a qubit is measured, it gets into one of two states with probability 1.
In the system with two qubits the quantum state of two qubits
is denoted by:
α00|00>+ α01 |01>+ α10|10>+ α11 |11>
where αi are complex numbers;
∑| αi|2=1 (25)
These qubits are connected using Bell state [
it will be in a state |0> with probability ½ and likewise in a state |1> also with probability ½.
The second qubit is measured; it will be in the same state as the first qubit when it was measured with probability 1. When n qubits are measured the true number of size n is got.
The tree height H>=2 is chosen. 2H documents are signed using one public key. A connection is established between two qubits using Bell state. 2H pairs of such qubits are token qubi and bi ; every qubi and bi consists of n qubits. 0<=i<=2H; 2H*n qubits qubi are measured and 2H signature keys are got Xi and the verification keys Yi are calculated. h(Yi) are calculated and are used as leaves of a tree.
Message m of arbitrary size, is transformed into size n by means of the hash function. h(m) = hash (26) Arbitrary set, that contains n qubits is measured, barb = qubarb=Xarb with probability equal to 1.
One-time signature is generated using one-time signature key Xarb, the document's signature will be the concatenation of onetime signature, one-time verification key Yarb, index arb and all fraternal nodes authi in relation to Yarb.
Signature= (sig||arb|| Yarb||auth0,…,authH-1) (27) Verification of the message occurs similarly to the standard Merkle system.
The principle of the crypto system is not changed, but only is integrated TRNG, to reduce the size of the signature key. TRNG is completely safe; it is based on the state of qubits, which are real random numbers.
So, the received scheme is absolutely secure.
2H pairs of one-time keys must be calculated in order to generate the public key in Merkle crypto system. It is not efficient to store these numbers of keys in practice. PRNG can be integrated to Merkle in order to reduce this number. Quantum computers can break PRNGs, that are used in many real-world crypto systems. Merkle crypto system with built-in PRNG can be vulnerable to attacks implemented on quantum computers. TRNG that is offered in the paper can be integrated to Merkle. In this case the system will be safe and the numbers of onetime key will be reduced.
The Work Was Conducted as a Part of Research Grant of Joint Project of Shota Rustaveli National Science Foundation and Science & Technology Center in Ukraine [№ STCU