Аналіз можливостей квантових комп’ютерів та квантових обчислень для криптоаналізу сучасних криптосистем

Автор(и)

  • Юрий Иванович Горбенко Харківський національний університет радіоелектроніки пр. Леніна, 16, м. Харків, Україна, 61166, Україна https://orcid.org/0000-0002-0652-8629
  • Роман Сергеевич Ганзя Харківський національний університет радіоелектроніки пр. Леніна, 16, м. Харків, Україна, 61166, Україна https://orcid.org/0000-0001-7945-3683

DOI:

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

Ключові слова:

алгоритм Гровера, алгоритм Шора, квантовий комп’ютер, квантовий криптоаналіз

Анотація

На основі використання доступних джерел наводиться  огляд та  аналіз сучасних світових досягнень в області квантових обчислень та побудови квантового комп’ютера. Проводиться аналіз загроз безпеки відносно симетричних та асиметричних криптосистем у разі застосування методів квантового криптоаналізу. Наводяться оцінки просторових та часових складностей, яких потрібно досягати для успішного здійснення  квантового криптоаналізу.

Біографії авторів

Юрий Иванович Горбенко, Харківський національний університет радіоелектроніки пр. Леніна, 16, м. Харків, Україна, 61166

Кандидат технічних наук, старший науковий співробітник

Кафедра безпеки інформаційних технологій

Роман Сергеевич Ганзя, Харківський національний університет радіоелектроніки пр. Леніна, 16, м. Харків, Україна, 61166

Інженер кафедри безпеки інформаційних технлогій

Кафедра безпеки інформаційних технологій

Посилання

  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.

##submission.downloads##

Опубліковано

2014-02-05

Як цитувати

Горбенко, Ю. И., & Ганзя, Р. С. (2014). Аналіз можливостей квантових комп’ютерів та квантових обчислень для криптоаналізу сучасних криптосистем. Eastern-European Journal of Enterprise Technologies, 1(9(67), 8–16. https://doi.org/10.15587/1729-4061.2014.19897

Номер

Том 1 № 9(67) (2014): Інформаційно-керуючі системи

Розділ

Інформаційно-керуючі системи

Ліцензія

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

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.