Post-Quantum Digital Signatures with Attenuated Pulse Generator Maksim Iavicha , Razvan Bocub , Arturo Arakelianc and Giorgi Iashvilia a School of technology Caucasus University Tbilisi, Georgia b Department of Mathematics and Computer Science Transilvania University of Brasov, Brasov, Romania c Informational technologies dept.University of Georgia Tbilisi, Georgia Abstract Quantum computations cause problems for classical systems. The perfect examples are effective 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 efficiency of the scheme is evaluated. Keywords cryptography, post-quantum, digital signatures, generation, pulse generator 1. Introduction 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", "Diffie-Hellman" and "eliptic curve cryp- nology 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 con- tion 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. Hash- the attacker uses classical computer with limited gen- based signature systems provide interesting alterna- eration 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 func- Quantum computers use not the same computational tions. Their safety is based on concrete hash func- methods. 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 se- key 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- 2. Hash-Based Signature Systems IVUS 2020: Information Society and University Studies, 23 April 2020, KTU Santaka Valley, Kaunas, Lithuania The template Hash-based signatures schemes were pre- " miavich@cu.edu.ge (M. Iavich); razvan.bocu@unitbv.ro (R. sented by Ralph Merkle. First of all, he offered “Lam- Bocu); arturo.arakelyan@gmail.com (A. Arakelian); port and Diffie” one-time signature [3]. Despite on giiashvili@cu.edu.ge (G. Iashvili) effectiveness of this signature scheme, size of signa-  © 2020 Copyright for this paper by its authors. Use permitted under Creative ture is long. The one-time signature of “Winternitz” Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) was offered. The main idea of this scheme is to sign Figure 1: Mertkle Tree 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 efficient, 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 efficient in practice. The scientists are work- In 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 offered 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 offer 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 offer 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 num- mation key. bers [7, 8, 9]. To get the seed for this CSPRNG we offer Both of them are string of bits. The leafs of Merkle to use the physical quantum random number genera- tree 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 op- children. 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 gen- erators during each measurement only one bit can be (2) received. In order to improve the efficiency photon 𝑘𝑝 [𝑗] = ℎ(𝑣ℎ−1 [2𝑗]||𝑣[ ℎ − 1][2𝑗 + 1]), 1 ≤ 𝑝 ≤ 𝐻 , 0 ≤ 𝑗 ≤ 2𝐻 −ℎ counting generators can be used. This type of gener- The process is illustrated on the Figure 2. ators are based on time effects. Attenuated pulse gen- erators are based on a simplified version of the previ- 43 ous approaches with much less requirements for the empty pulses or two successive clicks are cancelled. detectors. Almost all the single photon detectors have We offer 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 Offered Scheme the smaller bins, which are concatenated. These ap- proaches need a weak source that outputs zero or one 4.1. Key Generation photons in the bin and there is negligible probability Signer selects 𝐻 ∈ 𝑁,𝐻 ≥ 2 (8) to generate two or more photons in this short period of time. OQRNGs with a weak source and with the same After that, he chooses key pairs, which must be gen- probability of generating or not generating the pho- erated. To generate the signature keys, first of all the ton. We need the complete system to produce a detec- signer has to generate the seed. The seed must be gen- tion probability of 1/2. A superposition of the empty erated using the quantum random number generator. and single photon states in the same spatio-temporal He uses the attenuated pulse generator for this. After- mode can be represented so that the quantum state of wards he uses the HASH_DBRG to generate the keys. our photon pulse is: This CSPRNG takes the seed received by attenuated pulse generator as the input and outputs the signa- 1/2 (|0⟩ + |1⟩)/(2 ) (3) ture keys. Afterwards he generates the corresponding verification keys. So, the signer generates 2𝐻 pairs of We get a 0 when the event is not detected and 1 one-time signatures “(𝑋𝑗 , 𝑌𝑗 ), 0 ≤ 𝑗 ≤ 2𝐻 ”. “𝑋𝑗 ” is when we get a click. The state does not have to get signature’s key and “ 𝑌𝑗 ” is a confirmation key. Us- only one photon. The superposition: ing these keys he can sign 2𝐻 documents. The keys are the strings of bits. To get the leaves of the tree, he hashes the verification keys by means of the the hash 1/21/2 |0⟩ + ∑ 𝛼𝑘 |𝑘⟩ with ∑∞ 2 𝑘=1 |𝛼𝑘 | = 1/2 (4) function: So we get ones from clicks and do not pay attention, ℎ ∶ {0, 1}∗ → {0, 1}𝑛 (9) if they are triggered by many or one photons. Coher- ent states give us this superposition and it is easy to To get the parent node, the concatenation of two reproduce them. The probability to get zero photons previous nodes is hashed. The root of the tree is the is: 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 2 𝑝(𝑛 = 0) = 𝑒 −|𝛼| children. Public key is a root of MSS. The probability to find the photons is: 𝑝(𝑛 ≥ 1) = 1 − 𝑒 −|𝛼| 2 (6) 4.2. Message Signature We have to find 𝛼 for which 𝑝(𝑛 = 0) = 𝑝(𝑛 ≥ 1), To sign a message, the signer hashes it and gets the which occurs for 𝛼 = 𝑙𝑛(21/2 ). hash of the n size. h (m) = hash, to sign the message, The Poissonian source where is used some one-time key 𝑋𝑎𝑟𝑏 . This key is calculated by means of CSPRNG using the same seed got from 𝜆𝑇 = 𝑙𝑛(2) ≈ 0.693 (7) the attenuated pulse generator. Afterwards he uses 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 at- Practically, the generator uses an efficient mean pho- tenuated pulse generator as the input and outputs the ton number at the detector 𝑓 𝜆 𝑇 , with an efficiency 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 ..., 𝑎𝑢𝑡ℎ , ..., 𝑎𝑢𝑡ℎ ) (10) 𝐻 −2 𝐻 −1 44 4.3. Signature Verification Our method also increases the security of the scheme and the scheme is safe against the attacks of quantum For the signature verification, the one-time signature computers. is verified using the verification key, if the verification is successful, all the needed nodes are computed using "auth", index "arb" and 𝑌𝑎𝑟𝑏 . Acknowledgments If the root of the tree is the same as the public key, the corresponding signature is correct The work was conducted as a part of PHDF-19-519 and the grant financed by Caucasus University. 4.4. Advantages The offered scheme does not save a large amount of References 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. Nico- ficient, 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 autonomous media capture devices, Multimedia 6. CONCLUSION Tools and Applications 78 (2019) 14091–14108. As the result, the secure digital signature scheme is [6] J. Buchmann, L. García., E. Dahmen, M. Döring, got, and it is secure against quantum computers at- E. Klintsevich, An improved merkle signature tacks. The scheme stores only the short seed of the at- scheme. in: Barua r., lange t. (eds) progress in cryp- tenuated pulse generator, which is a secure quantum tology, volume 4329, 2006. random number generator. [7] A. Gagnidze, M. Iavich, G. Iashvili, Novel version The scheme uses HASH_DBRG as CSPRNG, this gen- of merkle cryptosystem, 2017. erator uses the quantum resistant hash function. This [8] G. Lo Sciuto, S. Russo, C. Napoli, A cloud-based random number received by attenuated pulse genera- flexible solution for psychometric tests validation, tor is used for HASH_DBRG pseudo random number administration and evaluation, in: CEUR Work- generator, which uses quantum secure hash function. shop Proceedings, volume 2468, 2019, pp. 16–21. This pseudo CSPRNG is very efficient and secure, and URL: www.scopus.com, cited By :1. it is NIST standard. As a seed HASH_DBRG uses a [9] Langdon, B. William, Prng random numbers on random number received by means of attenuated pulse gpu, 2017. generator. The integration of attenuated pulse genera- tor does not the influence on the efficiency, 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 effected. 45