Testing of code-based pseudorandom number generators for post-quantum application
DOI:
https://doi.org/10.30837/rt.2020.1.200.06Keywords:
post-quantum cryptography, provable secure generator, code-based cryptography, syndrome decodingAbstract
Recent advances in quantum computing based on new principles and phenomena of quantum mechanics show that quantum cryptanalysis of modern cryptographic algorithms can become real in the coming years. For example, according to the forecasts of the US National Institute of Standards and Technology (NIST) in the next decade, quantum cryptanalysis of most asymmetric cryptosystems used today will be available. For this reason, NIST announced a contest of post-quantum (i.e., resistant to quantum cryptanalysis) cryptographic algorithms for directional encryption, electronic signature, and key encapsulation. In the coming years, standardization of the selected algorithms and their early implementation is expected. Obviously, other cryptographic algorithms, for example, pseudorandom number generators based on solving complex theoretical problems (discrete logarithm, factorization, etc.), will also be subject to further revision. These generators must also be replaced by reliable and safe algorithms suitable for use even in the conditions of the possible application of quantum cryptanalysis (i.e., in the post-quantum period). This paper is devoted to the study of provably secure generators whose resistance is based on the complexity of solving the syndrome decoding problem. This structure allows the generators to keep the resistance to both classical cryptanalysis and cryptanalysis using quantum computing. The design features of classic code-based generator representative proposed by Fisher and Stern are presented, and a new generator scheme is proposed to overcome the drawback of its predecessor, such as a reduced practical maximum period length, by using a linear feedback shift register. Within this paper Results of heuristic testing of the above-mentioned generators is conducted in terms of the sequence period, the speed of sequence generation, the cryptographic resistance of the generators and the possibility of their use in the post-quantum period.References
Johnston D. Random Number Generators-Principles and Practices // Sep. 2018. doi:10.1515/9781501506062.
Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography. CRC-Press, 1996. 816 p.
Perlner R. A., Cooper D.A. Quantum Resistant Public Key Cryptography: A Survey IDtrust ’09, April 14- 16, 2009, Gaithersburg, MD, pp. 85-93. URL: https://ws680.nist.gov/publiсаtion/get_pdf.cfm?pub_id= 901595
Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner and Daniel Smith-Tone. NISTIR 8105. Report on Post-Quantum Cryptography. National Institute of Standards and Technology, Internal Report 8105, April 2016. 10 p.
Elaine Barker and John Kelsey. Recommendation for random number generation using deterministic random bit generators. National Institute of Standards and Technology, January 2012. 124 p. URL: https://doi.org/10.6028/NIST.SP.800–90A
Jean-Dernard Fisher, Jacques Stern. An efficient PseudoRandom Generator Provably as Secure as Syndrome Decodingґ // EUROCRYPT’96 Proceeding, LNCS 1070. Р. 245–255.
Andrea Rock. Pseudorandom Number Generators for Cryptographic Applications // Diplomarbeit zur Erlangung des Magistergrades an der Naturwissenschaftlichen Fakultat der Paris-Lodron-Universitat Salzburg. Salzburg. 2005.
Hastad J. Pseudorandom number generators from any one-way function / J. Hastad, R. Impagliazzo, L.A. Levin, M. Luby // SIAM Journal on Computing. 1999.Vol. 28. Р.1364-1396.
Kuznetsov A., Kavun S., Panchenko V., Prokopovych-Tkachenko D., Kurinniy F. and Shoiko V. Periodic Properties of Cryptographically Strong Pseudorandom Sequences // 2018 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018. Р. 129-134. doi: 10.1109/INFOCOMMST.2018.8632021
Dubrova E. (2009). How to speed-up your NLFSR-based stream cipher. 878 – 881. 10.1109/DATE.2009.5090786.
Kuznetsov A.A., Kiian A.S., Prokopovich-Tkachenko D.I., Zverev V.P., Kotuh E.V., Kuznetsova T.Y. Periodical properties of cryptographic resistance pseudorandom sequences // Applied redioelectronics: sci.-tech. magazine. 2018. Vol.17, №. 3, 4. Р. 96–103.
Grover L. A fast quantum mechanical algorithm for database search // Proceedings of the 28th annual ACM symposium on the theory of computing (STOC, 96). ACM Press, New York. 1996. P. 212–219.
Stipcevic M., Koc C.K. True random number generators // Open Problems in Mathematics and Computational Science. Springer, 2014. Р. 275–315.
Grover L. A fast quantum mechanics algorithm for database search», Proceeding of the 28th ACM Symposium on Theory of Computation. New York: ACM Press, 1996. Р. 212-219.
S. P. W: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // S IAM J. Comput, 1997.
Andrew Rukhin. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, URL: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf
Vlad Gheorghiu, Michele Mosca. Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes,URL: https://arxiv.org/pdf/1902.02332.pdf
Blum M.. How to generate cryptographycally strong sequences of pseudorandom bits / M. Blum, S. Micali // SIAM Journal on Computing. 1986. Vol. 1. Р.850-864.
Downloads
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
