Analysis of the possibility of quantum computers and quantum computings for cryptanalysis of modern cryptosystems

Authors

DOI:

https://doi.org/10.15587/1729-4061.2014.19897

Keywords:

quantum computer, Shor's algorithm, Grover's algorithm, quantum cryptanalysis, NTRU

Abstract

The main trends of the science and technology development in the field of quantum physics and quantum calculations are considered in the paper. It has been shown that over the past few years plenty of new discoveries and achievements have been made in the field of quantum physics, all these events, anyway, had a great influence on the invention and production of quantum computers. Many communities around the world have been engaged in the development of quantum computers and some of them have achieved significant results in it by now.

It is shown that using quantum algorithms of Shor and Grover, which can be fulfilled on a properly implemented quantum computer, can compromise some symmetric and asymmetric cryptosystems. The analysis results of endurance of the known block ciphers regarding the quantum cryptanalysis are given. It is also shown that some of them are not able to resist the quantum cryptanalysis method based on Grover's algorithm. The analysis of Shor's algorithm possibilities, which can significantly reduces computational costs for solving mathematical problems of endurance of modern asymmetric cryptoalgorithms, is given. Herewith, Shor's quantum algorithm diminishes the complexity of the cryptanalysis from exponential and subexponential to polynomial. In addition, the assessment of quantum computer resources is given in the paper, which are necessary for the quantum cryptanalysis concerning such cryptosystems as DSA, RSA, EC and NTRU.

Author Biographies

Юрий Иванович Горбенко, Kharkiv National University of Radio Electronics Lenina 16, Kharkov, Ukraine, 61166

Ph.D., senior research fellow

Department of Information Security Technologies

Роман Сергеевич Ганзя, Kharkiv National University of Radio Electronics Lenina 16, Kharkov, Ukraine, 61166

Engineer of the Department of  Information Security Technologies

Department of  Information Security Technologies

References

  1. Feyman, R. P. Quantum mechanical computers [Text] / R. P. Feyman // Opt. News – 1985. - February.11. - P.. 11-39.
  2. Горбенко, І. Д. Прикладна криптологія. [Текст]: монографія / І. Д. Горбенко, Ю. І. Горбенко; ХНУРЕ. – Х.: Форт, 2012. - 868 с.
  3. Deutsch, D. Rapid Solution of problems by quantum computation [Text] / Deutsch, D. , Jozsa R. // Proc. R. Soc. Lond. A. – 1992. – Vol. 439 (1907). – P.553-558.
  4. Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [Text] / P. W. Shor //SIAM J. Comput. - 1997. - 26 (5). - P. 1484–1509.
  5. Grover, L. K. A fast quantum mechanics algorithm for database search [Text] / L. K. Grover. // - Proceeding of the 28th ACM Symposium on Theory of Computation, New York: ACM Press. – 1996. - P. 212-219.
  6. Quantum computer built inside diamond [Electronic resource] / Futurity Research news from top universities- Режим доступа: www/ URL: – http://www.futurity.org/quantum-computer-built-inside-diamond/ - 09.04.2012.
  7. Dalfovo, F. V. Theory of Bose-Einstein condensationin trapped gases [Text] / Dalfovo F. , Giorgini S. , Pitaevskii L. P. , Stringari S. // Rev. Mod, Physics. – 1998 -71, No3. - P. 463-510.
  8. IBM Research Advances Device Performance for Quantum Computing [Electronic resource] / NY. IBM news - Режим доступа: www/ URL: – http://www-03.ibm.com/press/us/en/pressrelease/36901.wss - 28.02.2012 р.
  9. Lockheed Martin piece about D-Wave technology [Electronic resource] / Burnaby, British Columbia, Canada Блог компанії D-Wave Режим доступа: www/ URL: – http://dwave.wordpress.com/2013/03/08/lockheed-martin-piece-about-d-wave-technology/. - 08.03.2013 р.
  10. FIPS-186-3. Digital signature standard: 2009 [Text]. 2009 – 07 – 19 - Gaithersburg, MD 20899-8900 - 2009 – 120 р.
  11. IEEE Std 1363.1-2008. IEEE Standard Specification for Public Key Cryptographic Tehniques Based on Hard Problems over Lattice [Text] . 2009 – 04 – 10 – NY: The Institute of Electrical and Electronics Engineers, Inc – 2009 – 69 p.
  12. Launching the quantum artificial intelligence lab [Electronic resource] / Блог компанії Google: Режим доступа: www/ URL: – http://googleresearch.blogspot.ru/2013/05/launching-quantum-artificial.html. 16.05.2012 р.
  13. Гайнутдинова, А. Ф. Квантовые вычисления [Текст]: метод.пособие. А. Ф. Гайнутдинова. – Казань: Казанский государственный университет, 2009, - 272 с.
  14. Lenstra H. W. Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory [Text] / H. W. Lenstra, Jr. and R. Tijdeman, eds.// Math. Centre Tract 154 - 1946 - P. 89-139.
  15. Proos, J. Shor’s discrete logarithm quantum algorithm for elliptic curves [Text] / Proos J., Zalka C. // QIC. – 2003. – Vol.4. – P. 317-344.
  16. Hoffstein, J. NTRU: A ring-based public key cryptosysytem [Text] / J. J. Pipher and J. Silverman // ANTS III. – 1998 – Vol.1423 – P. 267-288.
  17. Silverman, J. A Meet-The Middle Attack on an NTRU Private Key [Text] / J. Silverman, J. Odlyzko // NTRU Cryptosysytems. - Technical Report, NTRU Report - 2003 - 004, Version 2. – 7 p.
  18. Ludwig, C. A faster lattice reduction method using quantum search [Text] / C. A. Ludwig // Algo Comput, - 2003 – Vol.2906. – P. 199-208.
  19. Wang, X. A quantum algorithm for searching a target solution of fixed weight [Text] / Wang, X. W. , S. Bao and X. Q. Fu // Chinese Sci Bull. - 2010.- Vol.55(29). – P.484-488.
  20. Xiong, Z. An Improved MITM Attack Against NTRU [Text] / Z. Xiong Wang J. , Wang Y. , Zhang T. , Chen L. // International Journal of Security and Its Applications. – 2012. - Vol. 6, No. 2. – P. 269-274.
  21. Wang, H. An efficient quantum meet-in-the-middle attack against NTRU-2005 [Text] / Wang Hong, MA Zhi, MA ChuanGui // Chinese Science Bulletin. – 2013. - Vol. 58, No.28-29. – P.3514-3518.
  22. Feyman, R. (1985). Quantum mechanical computers. Opt. News, February 11., 11-39.
  23. Gorbenko, I. D., Gorbenko, U. I. (2012). Applied cryptology. KNURE. Kharkov: Fort, 868.
  24. Deutsch, D., Jozsa, R. (1992). Rapid Solution of problems by quantum computation. Proc. R. Soc. Lond. A. Vol. 439, 553-558.
  25. Shor, P. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., 26 (5),1484–1509.
  26. 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, 212-219.
  27. Perkins, R. (2012). Quantum computer built inside diamond. Futurity Research news from top universities. Available at: http://www.
  28. futurity.org/quantum-computer-built-inside-diamond/
  29. Dalfovo, F. (1998).Theory of Bose-Einstein condensationin trapped gases Rev. Mod. Physics, 71, No 3, 463-510.
  30. Heights, Y. (2012). IBM Research Advances Device Performance for Quantum Computing. IBM news. Available at: http://www-03.ibm.com /press/us/en/pressrelease/36901.wss
  31. Geordie, R. (2012). Lockheed Martin piece about D-Wave technology. Burnaby, British Columbia, Canada, The blog of D-Wave. Available at: http://dwave.wordpress.com/2013/03/08/lockheedmartin-piece-about-d-wave-technology/.
  32. FIPS-186-3 (2009). Digital signature standard: 2009. Gaithersburg, MD 20899-8900, 120.
  33. 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.
  34. Neven, H. (2013). Launching the quantum artificial intelligence lab. THE Blog of Google. Available at: http://googleresearch.blogspot.ru/ 2013/05/launching-quantum-artificial.html
  35. Gaynutdinova, A. (2009). Quantum Computing. Kazan: Kazan State university, 272.
  36. Lenstra, H., Tijdeman, Jr., Tijdeman, R. (1946). Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory. Math. Centre Tract 154, 89-139.
  37. Proos, J., Zalka, C. (2003). Shor’s discrete logarithm quantum algorithm for elliptic curves. QIC, Vol. 4, 317-344.
  38. Hoffstein, J., Silverman, J. (1998). NTRU: A ring-based public key cryptosysytem. ANTS III, Vol. 1423, 267-288.
  39. Silverman, J., Odlyzko, J. (2003). Meet-The Middle Attack on an NTRU Private Key. NTRU Cryptosysytems: Technical Report, NTRU Report, Version 2, 7.
  40. Ludwig, C. (2003). A faster lattice reduction method using quantum search. Algo Comput, Vol. 2906, 199-208.
  41. Wang, X., Bao, W., Fu, X. (2010). A quantum algorithm for searching a target solution of fixed weight. Chinese Sci Bull, Vol. 55 (29), 484-488.
  42. Xiong, Z., Wang, J., Wang, Y., Zhang, T., Chen, L. (2012). An Improved MITM Attack Against . International Journal of Security and Its Applications, Vol. 6, No. 2, 269-274.
  43. Wang, H., Zhi, M. A., ChuanGui, M. A. (2013). An efficient quantum meet-in-the-middle attack against NTRU-2005. Chinese Science Bulletin, Vol. 58, No.28-29, 3514-3518.
  44. Ludwig, C. (2003). A faster lattice reduction method using quantum search. Algo Comput, Vol.2906, 199-208.
  45. Wang, X., Bao, W., Fu, X. (2010). A quantum algorithm for searching a target solution of fixed weight. Chinese Sci Bull, Vol. 55 (29), 484-488.
  46. Xiong, Z., Wang, J., Wang, Y., Zhang, T., Chen, L. (2012). An Improved MITM Attack Against . International Journal of Security and Its Applications, Vol. 6, No. 2, 269-274.
  47. 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, 3514-3518.

Downloads

Published

2014-02-05

How to Cite

Горбенко, Ю. И., & Ганзя, Р. С. (2014). Analysis of the possibility of quantum computers and quantum computings for cryptanalysis of modern cryptosystems. Eastern-European Journal of Enterprise Technologies, 1(9(67), 8–16. https://doi.org/10.15587/1729-4061.2014.19897

Issue

Vol. 1 No. 9(67) (2014): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2014 Юрий Иванович Горбенко, Роман Сергеевич Ганзя

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.