УДК 519.7
ДОСТИЖИМАЯ ВЕРХНЯЯ ГРАНИЦА SUP-НОРМЫ ПРОИЗВЕДЕНИЯ
ЭЛЕМЕНТОВ КОЛЬЦА УСЕЧЕННЫХ МНОГОЧЛЕНОВ
И ЕЕ ПРИМЕНЕНИЕ К АНАЛИЗУ NTRU-ПОДОБНЫХ КРИПТОСИСТЕМ
Аннотация. Получен ответ на вопрос, поставленный в 2008 г. В. Любашев-ским,
об эффективном алгоритме вычисления параметра
θ ( f ), характеризу-ющего величину sup-нормы
произведения элементов кольца усеченных мно-гочленов по модулю заданного унитарного
многочлена
f ( x ) с вещественны-ми коэффициентами. Рассмотрено применение полученных результатов
к оцениванию вероятности ошибочного расшифрования сообщений в NTRU-подобных криптосистемах.
Ключевые слова: решеточная криптография, кольцо усеченных многочле-нов, sup-норма произведения многочленов,
NTRU-подобная криптосистема, вероятность ошибочного расшифрования.
ПОЛНЫЙ ТЕКСТ
Алексейчук Антон Николаевич,
доктор техн. наук, доцент, профессор кафедры Национального технического университета Украины «Киевский политехнический институт имени Игоря Сикорского»,
alex-dtn@ukr.net
Матийко Александра Андреевна,
преподаватель Национального технического университета Украины «Киевский политехнический институт имени Игоря Сикорского»,
alexm1710@ukr.net
СПИСОК ЛИТЕРАТУРЫ
- Albrecht M.R., Curtis B.R., Deo A., Davidson A., Player R., Postlethwaite E.W., Virdia F., Wunderer T. Estimate all the {LWE, NTRU} schemes! Cryptology ePrint Archive, Report 2018/331. URL: http://eprint.iacr.org/2018/331.
- Lyubashevsky V. Towards practical lattice-based cryptography, Ph.D, 2008. URL: https://escholarship/ org/uc/item/0141w93p.
- Картан А. Дифференциальное исчисление. Дифференциальные формы / Пер. с франц. Москва: Мир, 1971. 392 с.
- Hoeffding W. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 1963. Vol. 58, N 301. P. 13–30.
- Hirschhorn P., Hoffstein J., Howgrave-Graham N., Whyte W. Choosing NTRU parameters in light of combined lattice reduction and MITM approaches. Applied Cryptography and Network Security, LNCS. 2009. Vol. 5536. P. 437–455.
- Hoffstein J., Pipher J., Schanck J.M., Silverman J.H., Whyte W., Zhang Z. Choosing parameters for NTRUEncrypt. Cryptology ePrint Archive. Report 2015/708. URL: http://eprint.iacr.org/2015/708.
- Chen C., Hoffstein J., Whyte W., Zhang Z. NIST PQ Submission: NTRUEncrypt. A lattice based algorithm. URL: https://cscr.nist.gov/Projects/Post-Quantum-Cryptography, 2017.
- Lyubashevsky V., Seiler G. NTTRU: Truly fast NTRU using NTT. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019. Vol. 3. P. 180–201.
- Матійко О.А., Олексійчук А.М. Оцінки помилкового розшифрування повідомлень у шифросистемі NTRUEncrypt при фіксованому ключі. Захист інформації. 2018. Т. 20, № 2. С. 89–94.