Оцінки ймовірності помилкового розшифрування повідомлень у шифросистемі 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.
Посилання
- Поки немає зовнішніх посилань.
ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована
