Достижимая верхняя граница sup-нормы произведения элементов кольца усеченных многочленов и ее применение к анализу NTRU-подобных криптосистем

Abstract

Получен ответ на вопрос, поставленный в 2008 г. В. Любашевским, об эффективном алгоритме вычисления параметра θ(f), характеризующего величину sup-нормы произведения элементов кольца усеченных многочленов по модулю заданного унитарного многочлена f(x) с вещественными коэффициентами. Рассмотрено применение полученных результатов к оцениванию вероятности ошибочного расшифрования сообщений в NTRU-подобных криптосистемах.

Отримано відповідь на питання, поставлене в 2008 р. В. Любашевським, про ефективний алгоритм обчислення параметра θ(f), що характеризує величину sup-норми добутку елементів кільця зрізаних поліномів за модулем заданого унітарного полінома f(x) з дійсними коефіцієнтами. Розглянуто застосування отриманих результатів до оцінювання ймовірності помилкового розшифрування повідомлень в NTRU-подібних криптосистемах.

The answer to the question posed in 2008 by V. Lyubashevsky about an efficient algorithm for calculating the parameter θ(f) that characterizes the value of the sup-norm of the elements’ product in the ring of truncated polynomials modulo a given mimic polynomial f(x) with real coefficients is obtained. The application of the obtained results to the estimation of decryption failure probability of messages in NTRU-like cryptosystems is considered.