Analysis of resistance popular cryptosystems against quantum cryptanalysis based on Grover's algorithm

Authors

  • Юрій Іванович Горбенко Kharkiv National University of Radio Electronics
  • Роман Сергійович Ганзя JSC «IIT»

DOI:

https://doi.org/10.18372/2410-7840.16.6915

Keywords:

Grover's algorithm, block symmetric cipher, NTRU, the ring of truncated polynomials, stability,

Abstract

The problem of resistance the popular cryptosystemsagainst quantum cryptanalysis is an urgent and importanttask, given the pace of development of quantum technologies.Resistance of all modern cryptosystems based on thecomplexity of solving certain mathematical problems. Suchmathematical problems tend to have exponential complexityor subexponential solutions, using quantum algorithmsthat have been proposed Shore and Grover the complexityof solving such problems is reduced to a polynomial. SoShor's algorithm reduces the complexity of cryptanalysistransformations in the ring, field and in the group of pointson elliptic curves. The article describes the using ofGrover's algorithm for cryptanalysis popular symmetricblock ciphers. The methods of quantum cryptosystemscryptanalysis NTRU, based on a combination of classicalattacks and meeting in the middle of Grover's quantumalgorithm. In this paper we proposed our estimates of resistanceof block popular ciphers and cryptosystemsNTRU with different sizes of the quantum system-wideparameters against cryptanalysis based on the use ofGrover's quantum algorithm. The article also shows thecharacteristics that must have a quantum computer forsuccessful cryptanalysis of certain cryptosystems.

Author Biographies

Юрій Іванович Горбенко, Kharkiv National University of Radio Electronics

Ph.D., senior research fellow ofKharkiv National University of Radio Electronics, Laureateof the State Prize in Science and Technology.

Роман Сергійович Ганзя, JSC «IIT»

analyst of security systems of JSC «IIT»

References

Shor, P. (1997), «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer», SIAM J. Comput., 26 (5), pp.1484-1509.

Grover, L. (1996),. «A fast quantum mechanics algorithm for database search», Proceeding of the 28th ACM Symposium on Theory of Computation. New York: ACM Press, pp. 212-219.

Perkins, R. (2012), «Quantum computer built inside diamond», Futurity Research news from top universities. Mode of access: http://www.futurity.org/quantum-computer-built-inside-diamond/.

Dalfovo, F. (1998), «Theory of Bose-Einstein condensationin trapped gases». Rev. Mod. Physics, 71, No3, pp. 463-510.

FIPS-186-3. (2009), Digital signature standard: 2009. Gaithersburg, MD 20899-8900, 120 p.

IEEE Std 1363.1-2008. (2009), IEEE Standard Specification for Public Key Cryptographic Tehniques Based on Hard Problems over Lattice. NY: The Institute of Electrical and Electronics Engineers, Inc., 69 p.

Gaynutdinova, A. (2009), «Quantum Computing», Kazan: Kazan State university, 272 p.

Silverman, J., Odlyzko, J. (2003), «Meet-The Middle Attack on an NTRU Private Key», NTRU Cryptosysytems: Technical Report, NTRU Report, Version 2, 7 p.

Wang, X., Bao, W., Fu, X. (2010), «A quantum algorithm for searching a target solution of fixed weight», Chinese Sci Bull, Vol.55(29), pp. 484-488.

Xiong, Z., Wang, J., Wang, Y., Zhang, T., Chen, L. (2012,. «An Improved MITM Attack Against NTRU», International Journal of Security and Its Applications, Vol. 6, No. 2, pp. 269-274.

Wang, H., Zhi, MA., ChuanGui, MA. (2013), «An efficient quantum meet-in-the-middle attack against NTRU-2005», Chinese Science Bulletin, Vol. 58, No.28-29, pp. 3514-3518.

Downloads

Published

2014-07-22

Issue

Vol. 16 No. 2 (2014)

Section

Articles

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).