Оцінки ймовірності помилкового розшифрування повідомлень у шифросистемі NTRUEncrypt при фіксованому ключі

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

Анотація


Асиметрична система шифрування NTRUEncrypt є однією з найшвидших постквантових шифросистем. На сьогодні відомо декілька версій цієї шифросистеми, проте усі вони володіють небажаною властивістю припускатися помилок розшифрування, що, поряд з незручностями для законних користувачів, приводить до  специфічних атак на шифросистему і, як наслідок, зменшує її стійкість. При традиційному підході до оцінювання ймовірності помилкового розшифрування вважається, що ця ймовірність визначається відносно випадкового вибору всіх елементів, які використовуються для формування шифротексту: відкритого тексту, ключа та так званого рандомізуючого полінома. Поряд з тим, з практичного погляду більш адекватним показником частоти виникнення помилок є набір ймовірностей, обчислених для кожного фіксованого значення секретного ключа. У даній статті отримано верхні оцінки ймовірності помилкового розшифрування повідомлень при фіксованому ключі для однієї з найпоширеніших версій шифросистеми NTRUEncrypt. Перша з двох отриманих оцінок є наближеною в тому сенсі, що при її доведенні здійснюється заміна розподілу ймовірностей суми певних незалежних випадкових величин граничним (нормальним) розподілом. Друга отримана оцінка доводиться за допомогою нерівності Гефдінга та не базується на жодних евристичних припущеннях. В цілому, отримані результати надають більш адекватну інформацію про частоту виникнення помилок при розшифруванні для розглянутої версії NTRUEncrypt та можуть бути використані в подальшому при виборі параметрів цієї шифросистеми для її оптимізації за стійкістю або практичністю.

 


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


постквантова криптографія; NTRUEncrypt; ймовірність помилкового розшифрування; центральна гранична теорема; нерівність Гефдінга

Посилання


American National Standard X9.98-2010. Lattice-based polynomial public key encryption algorithm, Part 1: key establishment, Part 2: data encryption. 2010.

D. Bernstein, Ch. Chuengsatiansup, T. Lange, Ch. Van Vredendaal, "NTRU Prime: redusing attack surface at low cost", Cryptology ePrint Archive, Report 2016/461. [Electronic re-source]. Online: http://eprint.iacr.org/2016/461.

C. Chen, J. Hoffstein, W. Whyte, Z. Zhang, "NIST PQ Submission: NTRUEncrypt. A lattice based algorithm". [Electronic resource]. Online: https://cscr. nist.gov/Projects/Post-Quantum-Cryptorraphy, 2017.

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

W. Hoeffding, "Probability inequalities for sums of bounded random variables", J. Amer. Statist. Assoc., Vol. 58, no. 301, pp. 13-30, 1963.

J. Hoffstein, J. Pipher, J.H. Silverman, "NTRU: a new high speed public key cryptosystem", Preprint, presented at the rump session of Crypto’96. 1996.

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

J. Hoffstein, J. Pipher, J.M. Schanck, J.H. Silverman, W. Whyte, Z. Zhang, "Choosing parameters for NTRUEncrypt", Cryptology ePrint Archive, Report 2015/708. [Electronic resource]. Online: http://eprint. iacr.org/2015/708.

N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J. Proos, J.H. Silverman, A. Singer, W. Whyte, "The impact of decryption failures on the security of NTRU encryption", Advanced in Cryptology, Crypto 2003, LNCS, Vol. 2729, pp. 226-246, 2003.

N. Howgrave-Graham, J.H. Silverman, W. Whyte, "Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3", Topics in Cryptology. CT-RSA 2005, LNCS, Vol. 3376, pp. 118-135, 2005.

N. Howgrave-Graham, J.H. Silverman, A. Singer, W. Whyte, "NAEP: provable security in the presence of decryption failures", Cryptology ePrint Archive, Report 2003/172. [Electronic resource]. Online: http://eprint. iacr.org/2003/172

J.A. Proos, Imperfect decryption and an attack on the NTRU encryption scheme, Cryptology ePrint Archive, Report 2003/002. [Electronic resource]. Online: http://eprint. iacr.org/2003/002.


Повний текст: 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