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.

Published

2014-07-22

Issue

Section

Articles