Analysis of resistance popular cryptosystems against quantum cryptanalysis based on Grover's algorithm
DOI:
https://doi.org/10.18372/2410-7840.16.6915Keywords:
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.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
How to Cite
Issue
Section
License
The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.
All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.
Copyright
Authors who publish their works in the journal:
-
retain the copyright to their publications;
-
grant the journal the right of first publication of the article;
-
agree to the distribution of their materials under the CC BY 4.0 license;
-
have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.
