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

Юрій Іванович Горбенко, Роман Сергійович Ганзя

Анотація


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


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory

Ulrich's Periodicals Directory