ШВИДКА РОЗРІЗНЮВАЛЬНА АТАКА НА ШИФРОСИСТЕМУ NTRUCipher+

Автор(и)

  • Антон Миколайович Олексійчук Інститут спеціального зв’язку та захисту інформації Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського»
  • Александра Андріївна Матійко Інститут спеціального зв’язку та захисту інформації Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського»

DOI:

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

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

постквантова криптографія, криптосистеми на решітках, розрізнювальна атака, дискретне перетворення Фур’є, NTRUEncrypt, NTRUCipher.

Анотація

Шифросистему NTRUCipher запропоновано в 2017 р. як симетричну версію алгоритму шифрування NTRUEncrypt, який є на сьогодні одним з найшвидших постквантових криптографічних алгоритмів, що базуються на решітках у евклідовому просторі. Метою побудови NTRUCipher є створення симетричної шифросистеми для практичних застосувань, стійкість якої, аналогічно асиметричним, базується на складності розв’язанні лише однієї обчислювальної задачі. Проведені попередні дослідження зазначеної шифросистеми, проте за їх рамками залишається питання про стійкість NTRUCipher відносно розрізнювальних атак, спрямованих на побудову статистичних критеріїв для розрізнення послідовностей шифрованих повідомлень шифросистеми та суто випадкових послідовностей. У даній статті показано, що шифросистема NTRUCipher та навіть її природне удосконалення – NTRUCipher+, запропоноване по аналогії з відомою обґрунтовано стійкою версією асиметричної криптосистеми NTRU, є вразливими відносно розрізнювальних атак. Запропоновано швидку розрізнювальну атаку на шифросистему NTRUCipher+ та (для окремого випадку) ще більш швидку модифікацію цієї атаки. Отримано аналітичні оцінки трудомісткості обох атак, з яких випливає, що вони мають поліноміальну часову складність та можуть бути реалізовані в режимі реального часу (для стандартного набору параметрів шифросистеми). Отримані результати свідчать про те, що для побудови симетричних NRTU-подібних криптосистем слід використовувати інші загальні конструкції.

Посилання

Alekseychuk А.N., Matiyko А.А. (2017), “ Estimates of the probability of reversibility of random polynomials used in the modified version of NTRU cryptosystem”, Radiotekhnica: All-Ukr. Sci. Interdep. Mag., Vol. 189, pp. 38 – 46.

Matiyko А.А. (2019), “The comparative analysis of NTRUCipher and NTRUEncrypt encryption schemes”, Mathimatical and computer modelling. Series: Technical science, Vol. 19, pp. 81 – 87.

Albrecht M.R., Curtis B.R., Deo A., Davidson A., Player R., Postlethwaite E.W., Virdia F., Wunderer T. (2018), “Estimate all the {LWE, NTRU} schemes!”, Cryptology ePrint Archive, Report 2018/331. http://eprint.iacr.org/2018/331.

Babai L. (2002), “The Fourier transform and equations over finite abelian groups”. http://people.cs.uchicago.edu/~laci /ren/fourier.pdf.

Diop S., Sane B.O., Seck M., Diarra N. (2018), “NTRU-LPR IND-CPA: a new ideal lattice-based scheme”, Cryptology ePrint Archive, Report 2018/109. http://eprint.iacr.org/2018/109.

Hirschhorn P., Hoffstein J., Howgrave-Graham N., Whyte W. (2009), “Choosing NTRU parameters in light of combined lattice reduction and MITM approaches”, Applied Cryptography and Network Security, LNCS, Vol. 5536, pp. 437 – 455.

Hoeffding W. (1963), “Probability inequalities for sums of bounded random variables”, J. Amer. Statist. Assoc., Vol. 58, № 301.

Hoffstein J., Pipher J., Silverman J.H. (1998), “NTRU: a new high speed public key cryptosystem”, Algorithmic Number Theory (ANTS III). LNCS, Vol. 1423, pp. 267 – 288.

Katz J., Lindell Y. (2015), “Introduction to modern cryptography”, CRC Press.

Stehle D., Steinfeld R. (2011), “Making NTRU as secure as worst-case problems over ideal lattices”, Advances in Cryptology – EUROCRYPT 2011. Proceedings. Springer-Verlag, pp.27–47.

Valluri M.R. (2017), “NTRUCipher-lattice based secret key encryption”, arXiv:1710.01928V2. 6/10/2017.

##submission.downloads##

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

2020-09-09

Номер

Том 22 № 3 (2020)

Розділ

Статті

Ліцензія

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

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

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

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