Quantum computations cause problems for classical systems. The perfect examples are efective quantum algorithms, which are causing problems for the most popular cryptosystems. These systems are considered safe for classical computers. Despite on releasing quantum computers all sensitive information should stay safe. This information should be encrypted in such way that will withstand quantum computers' attacks. Classical cryptography consists of problems and instruments: encryption, key distribution, digital signatures, pseudo-random number generator and one-way functions. For example, "RSA" is safe only when factorization is hard for classical computer, but quantum computers can easily solve this problem. Hash-based signature systems provide interesting alternatives. Hash-based signatures systems use cryptographically secure hash functions. Their security is based on the security of the concrete hash function. Using secure hash function is the minimal requirement for safe digital signature's system, which can be used for signing many documents using one secret key. In the article we provide the improved hash based digital signature scheme. The scheme uses the secure pseudo random number generator. As the seed for this pseudo random number generator it uses the truly random number received using attenuated pulse quantum generator. The security and the eficiency of the scheme is evaluated.
ries are: factorization and the equation of "Pell". Using these algorithms means that quantum computers can Nowadays digital signatures become main security tech- hack: "RSA", "Difie-Hellman" and "eliptic curve crypnology for the internet and for other IT infrastruc- tography", which nowadays are widely in use. tures. Digital signatures are widely used for identifica- "Buchmann-Williams" is also widely used and contion and authentication in protocols. That’s why safe sidered as safe system. Nowadays the main question signature algorithms are very important [1, 2]. It is is, which cryptosystem will be safe against quantum rather very hard to make the new crypto-system. The computes’ attacks. Nowadays signature algorithms that goal is to create such system, which would satisfy all are used in practice are: RSA, DSA and ECDSA. They safety standards. During creating a new system we can are not protected from quantum computers, because only assume the computational resource. Supposedly of they are based on factorization’s algorithm. Hashthe attacker uses classical computer with limited gen- based signature systems provide interesting alternaeration time. But, if he uses a quantum computer, then tives. As well as other signature systems, hash-based we have to identify which crypto systems are secure. signatures systems are using cryptographical hash funcQuantum computers use not the same computational tions. Their safety is based on concrete hash funcmethods. Some submodules like quantum "Fourier’s" tion’s safety. Using safe hash function is the minimal transformation will act faster on quantum computer requirement for safe digital signature’s system, which than on classical computer. In cryptography public- can be used for signing many documents using one sekey is used for securing transactions, its safety is based cret key. on the couple hard theories. Quantum computers can break these theories. Couple examples of such theo
sented by Ralph Merkle. First of all, he ofered “Lamport and Difie” one-time signature [3]. Despite on efectiveness of this signature scheme, size of signature is long. The one-time signature of “Winternitz” was ofered. The main idea of this scheme is to sign multiple bits of one message simultaneously. In real 2 pairs of one time keys must be calculated to get life one-time signatures are not eficient, because us- the public key. Storing such a large number of keys is ing one key we can generate only one signature [4, 5]. very not eficient in practice. The scientists are workIn 1979 Ralph Merkle introduced solution of this issue. ing on improving the scheme. They to integrate pseudo His idea is to use whole binary tree where public key random number generator – PRNG into the scheme is the root if this tree. [6]. This is ofered not to compute and not to save
Merkle signature scheme (MSS) is working with any large amounts of one-time keys pairs. hash functions and with any one-time signature schemes CSPRNGs are pseudo random number generators, For example, we have "ℎ ∶ {0, 1}∗ → {0, 1} " which is which are secure for use cryptography. A lot of PRNGs a hash function also let’s say we have some one-time are not quantum resistant, so we ofer an algorithm signature scheme. based on a secure hash function, as the entire the al
Signer selects H ∈ N, H ≥ 2. After that he chooses gorithm is based on it. key pair, which will be generated. We ofer to use HASH_DBRG, because it is rather ef
Using these, he can sign 2 documents. Signer gen- ficient, is based also on hashing and is NIST standard. erates 2 times pair of one-time signatures ( , ), As a seed to pseudo random number generators it is 0 ≤ ≤ 2 . is signature’s key and is a confir- recommended to use the true random number nummation key. bers [7, 8, 9]. To get the seed for this CSPRNG we ofer
Both of them are string of bits. The leafs of Merkle to use the physical quantum random number generatree are tor (QRNG).
0 ≤ ≤ 2
(1) ℎ( ), 3. Attenuated Pulse Generators Merkle tree leafs are calculating in such way: value of parent leaf is hash of concatenation of left and right Today, most of QRNGs are based on the quantum opchildren. Public key is a root of MSS. Private key of tics. Time of arrival generators are optical quantum MSS is a 2 one-time signatures’ sequence: random number generators - OQRNGs. In these generators during each measurement only one bit can be [ ] = ℎ( ℎ−1[2 ]|| [ℎ − 1][2 + 1]), (2) received. In order to improve the eficiency photon 1 ≤ ≤ , 0 ≤ ≤ 2 −ℎ counting generators can be used. This type of generThe process is illustrated on the Figure 2. ators are based on time efects. Attenuated pulse generators are based on a simplified version of the previous approaches with much less requirements for the empty pulses or two successive clicks are cancelled. detectors. Almost all the single photon detectors have We ofer to use attenuated pulse generators as a seed rather limited photon number resolving capability and of HASH_DBRG get the response by clicking or not clicking. Photon counting approaches rely on multiple clicks occurred in a long period of time. This period is divided into 4. The Ofered Scheme the smaller bins, which are concatenated. These approaches need a weak source that outputs zero or one 4.1. Key Generation photons in the bin and there is negligible probability Signer selects ∈ , (8) to generate two or more photons in this short period of time. OQRNGs with a weak source and with the same probability of generating or not generating the photon. We need the complete system to produce a detection probability of 1/2. A superposition of the empty and single photon states in the same spatio-temporal mode can be represented so that the quantum state of our photon pulse is:
if they are triggered by many or one photons. Coherent states give us this superposition and it is easy to reproduce them. The probability to get zero photons is:
( = 0) = −| |2
( ≥ 1) = 1 − −| |2 ℎ ∶ {0, 1}∗ → {0, 1} (9)
To get the parent node, the concatenation of two previous nodes is hashed. The root of the tree is the public key of the signature - public. Merkle tree leafs are calculated in such way: value of the parent leaf (5) is the hashed value of concatenation of left and right
children. Public key is a root of MSS. (6)
4.2. Message Signature
We have to find for which ( = 0) = ( ≥ 1), To sign a message, the signer hashes it and gets the whTichhe oPcociussrosnfioarn so=urc(e2w1/2h)e. re ihsaushseodfstohmeenosnizee-t.i mhe(mke)y= h ash. ,Tthoissikgenytihsecamlceusslaatgeed, by means of CSPRNG using the same seed got from (7) the attenuated pulse generator. Afterwards he uses = (2) ≈ 0.693 the HASH_DBRG to generate the signature keys once also gives the need probability of the detector. more. This CSPRNG takes the seed received by atPractically, the generator uses an eficient mean pho- tenuated pulse generator as the input and outputs the ton number at the detector , with an eficiency f. signature keys. The signature is a set of the one-time
This OQRNG can be balanced by fine tuning of a signature, one-time verification key, its index, and all variable attenuator. On the other hand, the generator fraternal nodes according to the selected arbitrary key can follow up on the light source. with the index “arb”
To get the random bit it can output 1 if 0 > 0 and 1 = 0 and outputs 0 if 0 = 0 and 1 > 0. Where and 0 and 1 are photon numbers Signature = ( ‖ ‖ ‖ℎ 0, ..., in two detections. The outcomes with 2 successive ..., ℎ −2, ..., ℎ
−1) (10)
is verified using the verification key, if the verification is successful, all the needed nodes are computed using "auth", index "arb" and .
If the root of the tree is the same as the public key, the corresponding signature is correct
The ofered scheme does not save a large amount of one-time keys pairs in the memory. The scheme stores only the short seed of the attenuated pulse generator, [1] G. C. Cardarilli, L. Di Nunzio, R. Fazzolari, M. Re, which is a secure quantum random number generator, Tdes cryptography algorithm acceleration using a attenuated pulse generator. The advantage of using reconfigurable functional unit, in: 2014 21st IEEE it approach is that during each measurement several International Conference on Electronics, Circuits random bits are received. As CSPRNG the system uses and Systems (ICECS), IEEE, 2014, pp. 419–422. HASH_DBRG, which is NIST standard and is rather ef- [2] S. Battiato, G. M. Farinella, C. Napoli, G. Nicoifcient, this CSPRNG uses the same secure hash func- tra, S. Riccobene, Recognizing context for privacy tion as the whole scheme does. preserving of first person vision image sequences, in: International conference on image analysis and processing, Springer, 2017, pp. 580–590. 5. SECURITY [3] M. Ajtai, Generating hard instances of lattice problems, volume 13 of Quad. Mat., 2004, pp. 1–32.
Algorithm of Merkle is almost the same, but the hash Dept. Math., Seconda Univ. Napoli, Caserta (2004). based CSPRNG is integrated, the seed for CSPRNG is Preliminary version in STOC 1996. 8. Babai, L.: generated using attenuated pulse generator. The of- On Lovász lattice reduction and the nearest lattice fered CSPRNG is secure against the attacks of quan- point problem. Combinatorica, 6:1*13 (1986). tum computers. The seed is received using quantum [4] A. Gagnidze, M. Iavich, G. Iashvili, Analysis of random number generator, so the proposed algorithm post-quantum cryptography use, 2017. of Merkles scheme is secure. [5] G. M. Farinella, C. Napoli, G. Nicotra, S. Riccobene, A context-driven privacy enforcement system for 6. CONCLUSION autonomous media capture devices, Multimedia Tools and Applications 78 (2019) 14091–14108. [6] J. Buchmann, L. García., E. Dahmen, M. Döring,
E. Klintsevich, An improved merkle signature scheme. in: Barua r., lange t. (eds) progress in cryptology, volume 4329, 2006. [7] A. Gagnidze, M. Iavich, G. Iashvili, Novel version
of merkle cryptosystem, 2017. [8] G. Lo Sciuto, S. Russo, C. Napoli, A cloud-based lfexible solution for psychometric tests validation, administration and evaluation, in: CEUR Workshop Proceedings, volume 2468, 2019, pp. 16–21.
URL: www.scopus.com, cited By :1. [9] Langdon, B. William, Prng random numbers on gpu, 2017.
got, and it is secure against quantum computers attacks. The scheme stores only the short seed of the attenuated pulse generator, which is a secure quantum random number generator.
The scheme uses HASH_DBRG as CSPRNG, this generator uses the quantum resistant hash function. This random number received by attenuated pulse generator is used for HASH_DBRG pseudo random number generator, which uses quantum secure hash function. This pseudo CSPRNG is very eficient and secure, and it is NIST standard. As a seed HASH_DBRG uses a random number received by means of attenuated pulse generator. The integration of attenuated pulse generator does not the influence on the eficiency, as it is used only for generating the seed for CSPRNG. So, in our approach the space need for storing the key is greatly reduces and the implementation speed is not efected.