=Paper=
{{Paper
|id=Vol-2698/paper07
|storemode=property
|title=Post-Quantum Digital Signatures with Attenuated Pulse
Generator
|pdfUrl=https://ceur-ws.org/Vol-2698/p07.pdf
|volume=Vol-2698
|authors=Maksim Iavich,Razvan Bocu,Arturo Arakelian,Giorgi Iashvili
|dblpUrl=https://dblp.org/rec/conf/ivus/IavichBAI20
}}
==Post-Quantum Digital Signatures with Attenuated Pulse
Generator==
https://ceur-ws.org/Vol-2698/p07.pdf
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