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

Автор(и)

  • Антон Миколайович Олексійчук Київський політехнічний інститут імені Ігоря Сікорського
  • Александра Андріївна Матійко Київський політехнічний інститут імені Ігоря Сікорського

DOI:

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

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

постквантова криптографія, 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.

##submission.downloads##

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

2018-06-25

Номер

Том 20 № 2 (2018)

Розділ

Статті

Ліцензія

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

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

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

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