Аналіз стійкості популярних криптоситем проти квантового криптоаналізу на основі алгоритму Гровера

Автор(и)

  • Юрій Іванович Горбенко Харківський національний університет радіоелектроніки
  • Роман Сергійович Ганзя ЧАО «ІІТ»

DOI:

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

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

алгоритм Гровера, блоковий симетричний шифр, NTRU, кільця зрізаних поліномів, стійкість,

Анотація

Проблема стійкості популярних криптосистем проти квантового криптоаналізу є актуальною і важливою задачею,враховуючи темпи розвитку квантових технологій. Стійкість всіх сучасних криптосистеми базується на складностівирішення певних математичних задач. Такі математичні задачі, як правило, мають субекспоненціальну або експо-ненціальну складність вирішення, використовуючи квантові алгоритми, які були запропоновані Шором та Гровером,складність вирішення таких задач зменшується до поліноміальної. Так, алгоритм Шора зменшує складність крип-тоаналізу перетворень в кільці, полі та в групі точок еліптичних кривих. У статті показана можливість викори-стання алгоритму Гровера для криптоаналізу популярних симетричних блокових шифрів. Розглянуто методи кван-тового криптоаналізу криптосистем NTRU, основані на комбінації класичної атаки зустріч посередині і квантовогоалгоритму Гровера. У роботі запропоновано наші оцінки стійкості популярних блокових шифрів і криптосистемNTRU з різними розмірами загальносистемних параметрів проти квантового криптоаналізу, що базується на вико-ристанні квантового алгоритму Гровера. Також у статті показано характеристики, якими повинен володіти кван-товий комп'ютер, для проведення успішного криптоаналізу певної криптосистеми.

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

Юрій Іванович Горбенко, Харківський національний університет радіоелектроніки

кандидат технічних наук, старший науковий співробітник Харківського націо-нального університету радіоелектроніки, лауреат Дер-жавної премії в галузі науки та техніки.

Роман Сергійович Ганзя, ЧАО «ІІТ»

аналітик систем захистуінформації ЧАО «ІІТ»

Посилання

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.

##submission.downloads##

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

2014-07-22

Номер

Том 16 № 2 (2014)

Розділ

Статті

Ліцензія

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).