Lattice based merkle Maksim Iavich Avtandil Gagnidze Giorgi Iashvili Sergiy Gnatyuk Vira Vialkova IT dept. School of Faculty of Business IT dept. School of IT Security dept. National dept.of Cyber Security Technology Management Technology Aviation University Taras Shevchenko National Caucasus University Int. Black Sea University Caucasus University Kyiv, Ukraine University Tbilisi, Georgia Tbilisi, Georgia Tbilisi, Georgia sergio.gnatyuk@gmail.com Kyiv, Ukraine m.iavich@scsa.ge gagnidzeavto@yahoo.com g.iashvili@scsa.ge veravialkova@gmail.com Abstract— Scientists are actively working on the creation of the possibility to check the true value of the information from quantum computers. Quantum computers can easily solve the problem the moment of digital signature formation. Digital signatures are of factoring the large numbers. As the result of it quantum computers very important in real life. The world leading scientists and are able to break the crypto system RSA, which is used in many experts are actively working on creating quantum computers. products. Hash based digital signatures are the alternative to RSA. Recently it is published an article claiming that the corporations These systems use cryptographic hash function. The security of these Google and NASA and Universities Space Research systems depends on the resistance to collisions of the hash functions Association (USRA) has signed an agreement on cooperation that they use. The paper analyzes hash based digital signature schemes. with the producer of D-Wave quantum processors. It is shown, that hash and one way functions must be used many times during the implementation of the hash based digital signature schemes. D-Wave 2X is the latest quantum processor, which contains Great attention must be paid on the security and the efficiency of these 2048 physical qubits. In this model of quantum computer 1152 functions. Hash functions are considered to be resistant to quantum qubits are used to perform calculations. Each additional qubit computer attacks, but the Grover algorithm allows us to achieve also enlarges twice the search space so increases the speed of the quadratic acceleration in the search algorithms. It means that hash calculations. functions must be complicated to be secure against quantum computers attacks. Scientists are working on determination of the cost of attacks Quantum computer will be able to destroy most of all or on SHA2 and SHA3 families of hash functions. It is recommended to completely all the traditional widely used cryptosystems, use lattice based constructions for one way and hash functions. Lattice concretely, systems based on the integer factorization task (e.g. based crypto systems are one of the alternatives to RSA. These crypto RSA). Some cryptosystems, such as RSA, with four thousand- systems have very reliable security evidence, based on "worst-case bit key are considered to be safe against the classical computers hardness", and are resistant to attacks of quantum computers. The attacks, but they are powerless against the quantum computer security of lattice based crypto system is based on the complexity of attacks. The security of digital signatures is based on the lattice problems, the main one of them is the shortest vector (SVP) complexity of discrete algorithm solution and the large integers problem. factorization problem. Quantum computers will easily overcome this problem and it will cause the breaking of digital It is proposed to use the lattice-based hash function instead of the standard one, and to use lattice based one-way function as a one-way signatures, implying the absolute failure. function in hash-based digital signature scheme. It is analyzed the II. LATTICE BASED CRYPTO SYSTEMS possibility of using the family of one-way functions, suggested by Ajtai. In this paper, it is proposed to use the one-way functions offered Lattice based crypto systems are one of the alternatives to by Ajtai and it can be considered as the initial idea. It is worth to RSA. These crypto systems have very reliable security consider the idea of using optimized one-way lattice based functions. evidence, based on "worst-case hardness", and are resistant to As the result we get the secure hybrid of lattice based and hash based attacks of quantum computers. The security of lattice based crypto systems, that can be used in post-quantum epoch. crypto system is based on the complexity of lattice problems, the main one of which is the shortest vector (SVP) problem Keywords— lattice, lattice-based crypto system, hash-based crypto system, Merkle crypto system [1-3]. A. Lattice based one-way functions. Ajtai offered a family of one-way functions with the security based on the worst cases of I. INTRODUCTION approximate SVP with accuracy nt, where t is an integer[4]. Digital signature is a requisite of the electronic document, Later Goldreich showed that this function is resistant to which is obtained by the cryptographic transformation and gives collisions, and it gives us the opportunity to use it as a hash function [5]. A lot of work is done to reduce the size of the © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) constant and in recent works the constant is already equal to 1. 13 The function has parameters n, m, a and b, which are integers. (f(sign-1), …, f(sig0)) = (yn-1[hashn-1], …, y0[hash0]) (8) The security of the function depends on the choice of n. In the case of hashing m must be greater than nlog a/ log b. If the equation is true, then the signature is correct. Matrix K from Zn×ma is chosen as a key. One-way function f For verification the one-way function f is used n times. works as follows: F. Winternitz one-time signature scheme. In the Lamport f(x) = Kx mod a. The function transforms mlog b into nlog a scheme key generation and signature generation are efficient, bit. As we can see, all the arithmetic can be performed very but the signature size is equal to n2. effectively without using the precision of integers commonly Winternitz one-time signature scheme is used to reduce the size used in cryptographic functions. [9]. In this scheme several bits of the hashed message are simultaneously signed by one line of the key. B. Hash-based crypto systems. Hash based digital signatures are also the alternative to RSA. These systems use cryptographic The Winternitz parameter is the number of bits of the hashed hash function. The security of these systems depends on the message that will be signed simultaneously. It is chosen as resistance to collisions of the hash functions, that they use [6,7]. w>=2. C. One-time signatures. Lamport–Diffie one-time signature After that we calculate: scheme. p1=n/w and p2= (log2p1 +1+w)/w, p= p1+ p2 (9) Lamport–Diffie one-time signature scheme was offered [8]. For the signature key X, 2n random lines of size n are generated. The signature keys are generated randomly: X= (xn-1[0], xn-1[1], …, x0[0], x0[1]) ∈ {0,1} n,2n (1) X= (xp-1[0], …, x0) ∈ {0,1} n,p (10) Verification key Y= (yn-1[0], yn-1[1], …, y0[0], y0[1]) ∈ {0,1} n,2n The verification key is computed as: It is calculated as follows: Y= (yp-1[0], …, y0) ∈ {0,1} n,p, 𝑤 where 𝑦𝑖 = 𝑓 2 −1 (𝑥𝑖 ), 0<=i<=p-1 (11) yi[j] = f(xi[j]), 0<=i<=n-1, j=0,1 (2) G. Signature of the message. The lengths of the signature and f – is one way function: the verification key are equal to np bits, one-way function f is used p(2w-1) times. f: {0,1} n {0,1} n; (3) To be signed the message is hashed: hash=h(m). The minimum As we see, for generating Y the one-way function f is used 2n number of zeros is added to the hash, so that the hash would be times. a multiple of w. Afterwards it is divided into p1 parts of size w. D. Signature of the message. To sign the message m, we hash: hash=kp-1,…, kp-p1 (12) h(m)=hash = (hashn-1, … , hash0) (4) The checksum: h- is a cryptographic hash function: с=∑i=p-p1p-1(2w-ki) (13) h: {0,1} *{0,1} n (5) As c<= p12w, the length of its binary representation is less than log2 p12w+1 The signature is calculated as follows: The minimum number of zeros is added the binary sig= (xn-1[hash n-1], …, x0[hash0]) ∈ {0,1} n,n (6) representation, so that it would be a multiple of w, and it is divided into p2 parts of the length w. The size of the signature is n2, one-way function f is not used. с=kp2-1,…, k0 (14) E. Message verification. To verify the signature sig, the message is hashed the message signature is calculated as follows: hash = (hashn-1, … , hash0) (7) 𝑠𝑖𝑔 = (𝑓 𝑘𝑝−1 (𝑥𝑝−1 ), … , 𝑓 𝑘0 (𝑥0 )) (15) After that the following equality is verified: 14 in the worst case f is used p(2w-1) times. The size of the signature is equal to pn. H. Signature Verification. To verify the signature sig = (sign-1, …, sig0) bit string kp-1,…, k0 are calculated. Then the following equality is verified: 𝑤 𝑤 (𝑓 2 −1−𝑘𝑝−1 (𝑠𝑖𝑔𝑛−1 ), … , (𝑓 (2 −1−𝑘0) )(𝑠𝑖𝑔0 ) = 𝑦𝑛−1 , … 𝑦0 (16) In the worst case function f must be used to verify the signature p(2w-1) times. Comparison of Lamport and Winternitz one-time signature schemes Lamport Winternitz Use f to generate 2n p(2w-1) keys Fig. 2. Merkle tree with H=3. Use f to calculate Is not used p(2w-1) the signature Use f to generate n p(2w-1) a[i,j] are the nodes of the tree; verify the signature a[1,0]=h(a[0,0] || a[0,1]) (17) Fig. 1. Comparison of signature schemes. The root of the tree is the public key of the signature - pub, 2H pairs of signature keys must be generated in order to calculate the public I. Merkle crypto-system. One time signatures are not convenient k, and the hash function h is used 2H+1-1 times. in use, because to sign each message a unique key is needed. The Merkle signature scheme allows to sign multiple messages K. Message signature. A message of any size can be signed being with the same key. This system uses one-time signature and a transformed to size of n by means of hashing h (m) = hash, binary tree a public key as a root. An arbitrary one-time key Xany is used, and the signature is a concatenation of one-time signature, one-time verification key, J. Key generation. The size of the tree must be H>=2 and using index of a key and all fraternal nodes according to the selected one public key 2H documents can be signed. Signature and arbitrary key with the index “any”. verification keys are generated; Xi, Yi, 0<=i<=2H. Xi- is the signature key, Yi- is the verification key. Signature keys are Signature= (sig||any|| Yany||auth0,…,authH-1) (18) hashed using the hash function h:{0,1}*{0,1}n in order to get the leaves of the tree. L. Signature verification. The one-time signature is checked using the selected verification key, if the verification is true, all the a[i, j] The concatenation of two previous nodes is hashed in order to are calculated using "auth", index "any" and Yany. The signature is get the parent node. verified, if the root of the tree matches the public key. The hash function in Merkle is used 2H+1-1 times, one-way function f is used 3p(2w-1) times in the case of Winternitz, and 3n times in the case of Lamport. Hash functions are considered resistant to quantum computer attacks, but the Grover algorithm allows us to achieve quadratic acceleration in the search algorithms. It means that hash functions must be complicated to be secure against quantum computers attacks. Studies are conducted to determine the cost of attacks on SHA2 and SHA3 families of hash functions [10]. 15 CONCLUSIONS [3]. Gagnidze A., Iavich M., Iashvili G., (2017) Analysis of post quantum cryptography use in practice. Bulletin of the Georgian We propose to use the lattice-based hash function and a lattice National Academy of Sciences, 2, 12: 29-36 based one-way function in hash-based digital signature [4]. Ajtai, M.: Generating hard instances of lattice problems. In schemes. Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1–32. Dept. Math., Seconda Univ. Napoli, Caserta (2004). The family of one-way functions, suggested by Ajtai, can be Preliminary version in STOC 1996. 8. Babai, L.: On Lovász lattice used. As the key of hash functions, the matrix K from Zn×ma is reduction and the nearest lattice point problem. Combinatorica, selected, it transforms mlog b into nlog a bits and h(x) is 6:1–13 (1986). calculated as Kx mod a. [5]. Goldreich, O., Goldwasser, S., and Halevi, S.: Collision-free hashing from lattice problems. Technical Report TR96-056, The matrix K from Zm×mb, is selected as the key of an one-way Electronic Colloquium on Computational Complexity (ECCC) function,. It transforms mlog b bits into mlog b bits and f(x) is (1996). computed as Kx mod a. [6]. Bernstein D.J., Buchmann J., Dahmen E., (2009) Book: One-way functions offered by Ajtai are proposed in the paper Introduction to post-quantum cryptography, Springer. [7]. Gagnidze A, Iavich M., Iashvili G., (2016) Some aspects of post- and it can be considered as the initial idea. It is worth quantum cryptosystems. Eurasian journal of business and considering the idea of using optimized one-way lattice based management, 5, 1: 16-20 functions. [8]. Lamport, L.: Constructing digital signatures from a one way function. Technical Report SRI-CSL-98, SRI International ACKNOWLEDGEMENT Computer Science Laboratory, 1979. The work was conducted as a part of joint project of Shota [9]. Merkle, R.C.: A certified digital signature. Advances in Rustaveli National Science Foundation of Georgia and Science Cryptology - CRYPTO ’89 Proceedings, LNCS 435, pages 218– & Technology Center in Ukraine [№ STCU-2016-08] 238, Springer, 1989. effectively without using the precision of integers commonly [10]. Wozniak, M., Polap, D., Borowik, G. and Napoli, C., 2015, July. A first attempt to cloud-based user verification in distributed used in cryptographic functions. system. In 2015 Asia-Pacific Conference on Computer Aided System Engineering, pp. 226-231 . IEEE. REFERENCES [11]. Amy M., Di Matteo O., Gheorghiu V., Mosca M., Parent A., Schanck J. (2017) Estimating the cost of generic quantum pre- image attacks on SHA-2 and SHA-3. Lecture notes in computer [1]. Güneysu T., Lyubashevsky V., Pöppelmann T. (2012) Practical Lattice-Based Cryptography: A signature scheme for embedded science, 10532: 10-31, Springer. systems. Lecture notes in computer Sci., 7428: 530-547, Springer. [2]. Akinyele, J.A., Garman, C., Miers, I. et al. (2013) Charm: a framework for rapidly prototyping cryptosystems. Journal of cryptographic engineering, 3. Springer: 111-128 16