=Paper=
{{Paper
|id=Vol-2470/p6
|storemode=property
|title=Lattice based merkle
|pdfUrl=https://ceur-ws.org/Vol-2470/p6.pdf
|volume=Vol-2470
|authors=Maksim Iavich,Avtandil Gagnidze,Giorgi Iashvili,Sergiy Gnatyuk,Vira Vialkova
|dblpUrl=https://dblp.org/rec/conf/ivus/IavichGIGV19
}}
==Lattice based merkle==
https://ceur-ws.org/Vol-2470/p6.pdf
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