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

• Published in: Кібернетика та системний аналіз
• Date: 2021
• Main Authors: Алексейчук, А.Н., Матийко, А.А.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2021
• Subjects: Кібернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/190644
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Достижимая верхняя граница sup-нормы произведения элементов кольца усеченных многочленов и ее применение к анализу NTRU-подобных криптосистем / А.Н. Алексейчук, А.А. Матийко // Кібернетика та системний аналіз. — 2021. — Т. 57, № 2. — С. 23–29. — Бібліогр.: 9 назв. — рос.

Получен ответ на вопрос, поставленный в 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.