- Scientists are actively working on the creation of quantum computers. Quantum computers can easily solve the problem of factoring the large numbers. As the result of it quantum computers are able to break the crypto system RSA, which is used in many products. Hash based digital signatures are the alternative to RSA. These systems use cryptographic hash function. The security of these systems depends on the resistance to collisions of the hash functions that they use. The paper analyzes hash based digital signature schemes. It is shown, that hash and one way functions must be used many times during the implementation of the hash based digital signature schemes. Great attention must be paid on the security and the efficiency of these functions. Hash functions are considered to be 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. Scientists are working on determination of the cost of attacks on SHA2 and SHA3 families of hash functions. It is recommended to use lattice based constructions for one way and hash functions. Lattice based crypto systems are one of the alternatives to RSA. These crypto systems have very reliable security evidence, based on "worst-case hardness", and are resistant to attacks of quantum computers. The security of lattice based crypto system is based on the complexity of lattice problems, the main one of them is the shortest vector (SVP) problem.
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 function in hash-based digital signature scheme. It is analyzed the 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 by Ajtai and it can be considered as the initial idea. It is worth to consider the idea of using optimized one-way lattice based functions. As the result we get the secure hybrid of lattice based and hash based crypto systems, that can be used in post-quantum epoch.
Digital signature is a requisite of the electronic document, which is obtained by the cryptographic transformation and gives © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
D-Wave 2X is the latest quantum processor, which contains 2048 physical qubits. In this model of quantum computer 1152 qubits are used to perform calculations. Each additional qubit also enlarges twice the search space so increases the speed of the calculations.
Quantum computer will be able to destroy most of all or completely all the traditional widely used cryptosystems, concretely, systems based on the integer factorization task (e.g. RSA). Some cryptosystems, such as RSA, with four thousandbit key are considered to be safe against the classical computers attacks, but they are powerless against the quantum computer attacks. The security of digital signatures is based on the complexity of discrete algorithm solution and the large integers factorization problem. Quantum computers will easily overcome this problem and it will cause the breaking of digital signatures, implying the absolute failure.
Lattice based crypto systems are one of the alternatives to
RSA. These crypto systems have very reliable security
evidence, based on "worst-case hardness", and are resistant to
attacks of quantum computers. The security of lattice based
crypto system is based on the complexity of lattice problems,
the main one of which is the shortest vector (SVP) problem
[
A. Lattice based one-way functions. Ajtai offered a family of
one-way functions with the security based on the worst cases of
approximate SVP with accuracy nt, where t is an integer[4].
Later Goldreich showed that this function is resistant to
collisions, and it gives us the opportunity to use it as a hash
function [
f – is one way function: yi[j] = f(xi[j]), 0<=i<=n-1, j=0,1 f: {0,1} n {0,1} n; As we see, for generating Y the one-way function f is used 2n times.
D. Signature of the message. To sign the message m, we hash: h- is a cryptographic hash function:
h: {0,1} * {0,1} n sig= (xn-1[hash n-1], …, x0[hash0]) ∈ {0,1} n,n The size of the signature is n2, one-way function f is not used. E. Message verification. To verify the signature sig, the message is hashed
hash = (hashn-1, … , hash0) After that the following equality is verified: The function has parameters n, m, a and b, which are integers. 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. Matrix K from Zn×ma is chosen as a key. One-way function f works as follows: f(x) = Kx mod a. The function transforms mlog b into nlog a bit. As we can see, all the arithmetic can be performed very effectively without using the precision of integers commonly used in cryptographic functions.
B. Hash-based crypto systems. Hash based digital signatures are
also the alternative to RSA. These systems use cryptographic
hash function. The security of these systems depends on the
resistance to collisions of the hash functions, that they use [
Winternitz one-time signature scheme is used to reduce the size
[
The Winternitz parameter is the number of bits of the hashed message that will be signed simultaneously. It is chosen as w>=2.
C. One-time signatures. Lamport–Diffie one-time signature
scheme.
Lamport–Diffie one-time signature scheme was offered [
Y= (yp-1[0], …, y0) ∈ {0,1} n,p, where = 2 −1( ), 0<=i<=p-1 G. Signature of the message. The lengths of the signature and the verification key are equal to np bits, one-way function f is used p(2w-1) times.
To be signed the message is hashed: hash=h(m). The minimum number of zeros is added to the hash, so that the hash would be a multiple of w. Afterwards it is divided into p1 parts of size w. h(m)=hash = (hashn-1, … , hash0)
The checksum: (1) (2) (3) (4) (5) (6) (7) (9) (10) (11) (12) (13) (14) (15) hash=kp-1,…, kp-p1 с=∑i=p-p1p-1(2w-ki) As c<= p12w, the length of its binary representation is less than 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.
( 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 2n
keys Use f to calculate Is not used the signature Use f to generate n verify the signature Fig. 1. Comparison of signature schemes.
Winternitz p(2w-1) p(2w-1) p(2w-1) I. Merkle crypto-system. One time signatures are not convenient in use, because to sign each message a unique key is needed. The Merkle signature scheme allows to sign multiple messages with the same key. This system uses one-time signature and a binary tree a public key as a root.
J. Key generation. The size of the tree must be H>=2 and using one public key 2H documents can be signed. Signature and verification keys are generated; Xi, Yi, 0<=i<=2H. Xi- is the signature key, Yi- is the verification key. Signature keys are hashed using the hash function h:{0,1}* {0,1}n in order to get the leaves of the tree.
The concatenation of two previous nodes is hashed in order to get the parent node.
Fig. 2. Merkle tree with H=3.
a[i,j] are the nodes of the tree;
a[
K. Message signature. A message of any size can be signed being transformed to size of n by means of hashing h (m) = hash, An arbitrary one-time key Xany is used, and the signature is a concatenation of one-time signature, one-time verification key, index of a key and all fraternal nodes according to the selected arbitrary key with the index “any”.
Signature= (sig||any|| Yany||auth0,…,authH-1) (18) L. Signature verification. The one-time signature is checked using the selected verification key, if the verification is true, all the a[i, j] are calculated using "auth", index "any" and Yany. The signature is 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].
CONCLUSIONS We propose to use the lattice-based hash function and a lattice based one-way function in hash-based digital signature schemes.
The family of one-way functions, suggested by Ajtai, can be used. As the key of hash functions, the matrix K from Zn×ma is selected, it transforms mlog b into nlog a bits and h(x) is calculated as Kx mod a.
The matrix K from Zm×mb, is selected as the key of an one-way function,. It transforms mlog b bits into mlog b bits and f(x) is computed as Kx mod a.
One-way functions offered by Ajtai are proposed in the paper and it can be considered as the initial idea. It is worth considering the idea of using optimized one-way lattice based functions.
ACKNOWLEDGEMENT The work was conducted as a part of joint project of Shota Rustaveli National Science Foundation of Georgia and Science & Technology Center in Ukraine [№ STCU-2016-08] effectively without using the precision of integers commonly used in cryptographic functions.