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

doi:10.18372/2410-7840.22.14981

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

Антон Миколайович Олексійчук, Александра Андріївна Матійко

Анотація

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

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

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

Посилання

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.

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