Hash Based Digital Signature Scheme with Integrated TRNG Maksim Iavich Avtandil Gagnidze Giorgi Iashvili Caucasus University Georia University Georia University Tbilisi, Georgia Tbilisi, Georgia Tbilisi, Georgia m.iavich@scsa.ge gagnidzeavto@yahoo.com g.iashvili@scsa.ge Abstract— The critical analysis of the existing hash based the problem of factoring large numbers and calculating digital signature schemes and their improvements is done in the discrete logarithms. Some cryptosystems for example RSA article. One of the improvements is integrating PRNG to Merkle system with four thousand bit keys are considered useful to crypto system. It is shown that integrating PRNG to Merke is protect information from attacks implemented on classical not safe, because quantum computers are able to break PRNG- s, that were considered safe against attacks implemented on computer, but are absolutely not protected against attacks classical computers. implemented using quantum computers [1,2]. RSA cryptosystem is used in many products on different TRNG based on qubits behavior is offered in the article and platforms and in different areas. To date, this cryptosystem is is offered to integrate this TRNG to Merkle. By means of the size of the signature key is reduced. integrated into many commercial products, the number of which is growing every day. RSA system is also widely used The principle of the crypto system is not changed, but only in operating systems from Microsoft, Apple, Sun, and Novell. TRNG is integrated. TRNG is completely safe; it is based on the In hardware performance RSA algorithm is used in secure state of qubits, which are real random numbers. So the received phones, Ethernet, network cards, smart cards, and is also scheme is secure. widely used in the cryptographic hardware. Along with this, the algorithm is a part of the underlying protocols protected Keywords—TRNG, hash-based, signature schemes, quantum, Internet communications, including S / MIME, SSL and S / cryptography WAN, and is also used in many organizations, for example, I. INTRODUCTION government, banks, most corporations, public laboratories and universities. Scientists and cyber security experts are actively working on the development of quantum computers. RSA BSAFE encryption technology is used approximately by 500 million users worldwide. Since in Google Corporation, Universities Space Research encryption technology is mostly used the RSA algorithm, it Association and federal agency NASA together with D- can be considered one of the most common public key WAVE, the manufacturer of quantum processors began to cryptosystems being developed together with the development work on creation of quantum processors. D-Wave 2X is a of the Internet. quantum processor that contains 2,048 physical qubits. Usually 1152 qubits are used to perform calculations. On this basis the RSA destruction will entail easy hacking of most products that can grow into a complete chaos Google is working on releasing the new CPU. Twenty qubit processor is already undergoing tests, and the company Active work is being conducted to create RSA alternatives, promises to have its working forty nine qubit chip ready by the which are protected from attacks by a quantum computer. end of this year. Until it began trialing the twenty qubit chip, Hash based digital signature schemes are considered as Google’s most powerful quantum chip was the nine qubit one of the RSA alternatives. These schemes use a effort from 2015. Each additional qubit doubles the data cryptographic hash function. The security of these digital search area, so the calculation speed is significantly signature schemes relies on the collision resistance of the hash Quantum computers will be able to break most, if not functions that they use [3,4]. Lamport–Diffie one-time absolutely all conventional cryptosystems, that are widely signature scheme Lamport–Diffie one-time signature scheme used in practice. is hash based digital signature scheme, and it is considered as alternative for the post-quantum era. So, traditional digital signature systems that are used presently in practice are vulnerable to attacks implemented on A. Keys generation quantum computers. The security of these systems is based on Copyright held by the author(s). 79 The signature key X of this system consists of 2n lines of Verification key is derived as following: length n, and the lines are selected randomly. 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. X= (xn-1[0], xn-1[1], …, x0[0], x0[1]) ∈ {0,1} n,2n (1) Verification key Y of this system consists of 2n lines of length F. Document signature n, and the lines are selected randomly. Y= (yn-1[0], yn-1[1], …, y0[0], y0[1]) ∈ {0,1} n,2n (2) To calculate the key we use one way function f: To sign the document, message must be hashed hash=h(m) f: {0,1} n {0,1} n; If length of hash is not devisable by w minimum number of yi[j] = f(xi[j]), 0<=i<=n-1, j=0,1 (3) zeros are prepended to hash and it is divided into s1 parts of length w. hash=ks-1,…, ks-s1 (12) B. Document signature: the checksum is calculated: с=∑i=s-s1s-1(2w-ki) (13) as c<= s12w, the length of its binary representation is Message m of arbitrary size, is transformed into size n by log2 s12w+1 (14) means of the hash function: If the length of representation is not devisable by w, the h(m)=hash = (hashn-1, … , hash0) (4) minimum number of zeros must be prepended to this binary Function h is a cryptographic hash function: representation and must be divided into s2 parts of length w. h: {0,1} *{0,1} n с=ks2-1,…, k0 (15) Signature occurs as follows: Finally, the signature of m is calculated: sig= (xn-1[hash n-1], …, x0[hash0]) ∈ {0,1} n,n (5) sig=(f^ks-1(xs-1), …, f^k0(x0)) (16) If the i-th bit in the message is equal to 0, i-th string in this The size of the signature is sn. 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 [1]. The length of the signature is n2. G. Signature verification C. Signature verification bit strings ks-1,…, k0 are calculated to verify the signature sig = (sign-1, …, sig0) (17) The following equality is checked: For signature verification sig = (sign-1, …, sig0), the hash of (f^(2w-1-ks-1))(sign-1), …, (f^(2w-1-k0))(sig0) = yn-1, … y0 (18) the message is calculated. If the signature is correct, then sigi =f^ki(xi) (19) hash = (hashn-1, … , hash0) and the following equality must (f^(2w-1-ki))(sigi)= (f^(2w-1))(xi)=yi ; i=s-1,…, 0 (20) be verified: (f(sign-1), …, f(sig0)) = (yn-1[hashn-1], …, y0[hash0]) (6) TABLE 1. LAMPORT AND WINTERNITZ If it is true, then the signature is correct. D. Winternitz one time signature scheme. Lamport Winternitz In Lamport one-time signature scheme, key generation and Key size 2n2 ns signature generation are quite effective, the size of the Using f for key 2n k(2w-1) signature is very large as it is equal to n2. Winternitz one-time generation signature scheme was proposed in order to decrease the Signature length n2 ns signature size. In Winternitz one-time signature scheme Using f for Not used k(2w-1) several bits of the hashed message are signed simultaneously signature with one string of the key, so the length of the signature is generation reduced significantly [5]. Using f for n k(2w-1) signature E. Keys generation verification The signature key X of this system consists of sn lines of length n, and the lines are selected randomly. The size of the signature in Winternitz one-time signature Winternitz parameter is selected w> = 2, it must be equal to scheme is significantly reduced ns=2, using one public Quantum computers are able to break PRNG-s, that were key 2H documents can be signed. 2H signature and considered safe against attacks implemented on classical verification key pairs are generated; Xi, Yi, 0<=i<=2H. Xi is computers. PRNG Blum-Micali turned out to be vulnerable the signature key, Yi is the verification key. h(Yi) are to polynomial quantum time attack. This PRNG is considered calculated and they are used as the leaves of the tree. Each safe from attacks implemented on standard computers. This tree node is a hash value of concatenation of its children. attack uses Grover algorithm along with the quantum discrete a[1,0]=h(a[0,0] || a[0,1]) (21) logarithm, and can restore the values at the generator output The root of the binary tree pub is the public key of the crypto for this attack. scheme. 2H pairs of one-time keys must be calculated in order to These type of attacks represent a threat of cracking PRNGs, generate the public key. 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 B. Signature generation using a true random number generator based on qubits, TRNG. Message m of arbitrary size, is transformed into size n by To construct this TRNG states and qubits must be considered. means of the hash function. h (m) = hash, and is generated a one-time signature using IV. QUANTUM TRNG 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. Information in a quantum computer is encoded in quantum bits or qubits. Like a bit, the qubit allows two eigenstates Signature= (sig||arb|| Yarb||auth0,…,authH-1) (22) (conditionally | 0> and | 1>), but unlike the bit, the qubit admits a superposition of these states, which means that it is more "informative" [9-11]. C. Signature verification In a system with one qubit, the quantum state of a qubit is To verify the signature, the one-time signature of sig is verified denoted by: 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 α|0>+β |1> compared with public key, if they are equal, then the signature is where α and β are complex numbers; correct. |α|2+ |β|2=1 (24) |0> - is the ground state of qubit |1>- is the excited state of qubit III. PRNG INTEGRATION TO MERKLE This qubit is in the state |0> with probability α2 and is in a state |1> with probability β2. 2H pairs of one-time keys must be calculated in order to generate When a qubit is measured, it gets into one of two states with the public key. Storing such a big number of key is problematic probability 1. in practice. In the system with two qubits the quantum state of two qubits To save the space, it was suggested to use the PRNG random is denoted by: number generator in Merkle signature scheme [8]. When using α00|00>+ α01 |01>+ α10|10>+ α11 |11> PRNG, only the seed of the generator must be stored and it must where αi are complex numbers; be used to generate one-time keys. In this case one-time keys ∑| αi|2=1 (25) 81 These qubits are connected using Bell state [12], in this case ACKNOWLEDGEMENTS the quantum state of these qubits is denoted by: The Work Was Conducted as a Part of Research Grant of 1/21/2|00>+1/21/2|11> Joint Project of Shota Rustaveli National Science Foundation When a given qubit is measured, it will be in a state |0> with probability ½ and likewise in a and Science & Technology Center in Ukraine [№ STCU- state |1> also with probability ½. 2016-08] The second qubit is measured; it will be in the same state as the first qubit when it was measured with probability 1. REFERENCES When n qubits are measured the true number of size n is got. [1] Bernstein D.J. (2009) Introduction to post-quantum cryptography. In: Bernstein D.J., Buchmann J., Dahmen E. (eds) A. Key generation Post-Quantum Cryptography. Springer, Berlin, Heidelberg [2] Avtandil Gagnidze, Maksim Iavich, Giorgi Iashvili, SOME ASPECTS OF POST-QUANTUM CRYPTOSYSTEMS, The tree height H>=2 is chosen. 2H documents are signed Eurasian Journal of Business and Management, 5(1), 2017, 16-20 using one public key. A connection is established between DOI: 10.15604/ejbm.2017.05.01.002 two qubits using Bell state. 2H pairs of such qubits are token [3] Dods C., Smart N.P., Stam M. (2005) Hash Based Digital qubi and bi ; every qubi and bi consists of n qubits. 0<=i<=2H; Signature Schemes. In: Smart N.P. (eds) Cryptography and 2H*n qubits qubi are measured and 2H signature keys are got Coding. Cryptography and Coding 2005. Lecture Notes in Xi and the verification keys Yi are calculated. h(Yi) are Computer Science, vol 3796. Springer, Berlin, Heidelberg [4] Dahmen E., Krauß C. (2009) Short Hash-Based Signatures for calculated and are used as leaves of a tree. Wireless Sensor Networks. In: Garay J.A., Miyaji A., Otsuka A. (eds) Cryptology and Network Security. CANS 2009. Lecture Notes in Computer Science, vol 5888. Springer, Berlin, B. Signature and verification of the message Heidelberg [5] A.Gagnidze, M.Iavich, N.Inasaridze, G.Iashvili Analysis of one- Message m of arbitrary size, is transformed into size n by time signature schemes // Scientific & practical cyber security means of the hash function. journal (SPCSJ) № 1.[Electronic journal]. URL: h(m) = hash (26) http://journal.scsa.ge/issues/2017/09/455 [6] Szydlo, M.: Merkle tree traversal in log space and time. In: Arbitrary set, that contains n qubits is measured, Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, barb = qubarb=Xarb with probability equal to 1. vol. 3027, pp. 541–554. Springer, Heidelberg (2004) One-time signature is generated using one-time signature key [7] Dods, C., Smart, N., Stam, M.: Hash based digital signature Xarb, the document's signature will be the concatenation of one- schemes. In: Smart, N.P. (ed.) Cryptography and Coding 2005. time signature, one-time verification key Yarb, index arb and all LNCS, vol. 3796, pp. 96–115. Springer, Heidelberg (2005) fraternal nodes authi in relation to Yarb. [8] Buchmann J., García L.C.C., Dahmen E., Döring M., Klintsevich E. (2006) CMSS – An Improved Merkle Signature Scheme. In: Signature= (sig||arb|| Yarb||auth0,…,authH-1) (27) Barua R., Lange T. (eds) Progress in Cryptology - INDOCRYPT Verification of the message occurs similarly to the standard 2006. INDOCRYPT 2006. Lecture Notes in Computer Science, Merkle system. vol 4329. Springer, Berlin, Heidelberg [9] Daniel F. V. James, Paul G. Kwiat, William J. Munro, and Andrew G. White Asymptotic Theory of Quantum Statistical C. Security Inference. February 2005, 509-538 The principle of the crypto system is not changed, but only is [10] U. Leonhardt, Measuring the quantum state of light (Cambridge integrated TRNG, to reduce the size of the signature key. University Press, 1997) [11] A. G. White, D. F. V. James, W. J. Munro and P. G. Kwiat, TRNG is completely safe; it is based on the state of qubits, “Exploring Hilbert Space: accurate characterization of quantum which are real random numbers. information,” submitted to Science (2001) So, the received scheme is absolutely secure. [12] Deng, FG., Li, XH., Li, CY. et al., Quantum state sharing of an arbitrary two-qubit state with two-photon entanglements and Bell-state measurements, PHYSICAL JOURNAL D, (2006) 39: D. Conclusion 459. https://doi.org/10.1140/epjd/e2006-00124-1 [13] Wozniak, M., Polap, D., Borowik, G. and Napoli, C., “A first 2H pairs of one-time keys must be calculated in order to generate attempt to cloud-based user verification in distributed system.” in Asia-Pacific Conference on Computer Aided System Engineering the public key in Merkle crypto system. It is not efficient to store (APCASE), 2015, pp. 226-231. 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 one- time key will be reduced. 82