NTRU: история, архитектура и безопасность

NTRU была изобретена Хоффстейном, Пайфером и Сильверманом в 1996 году, что делает её одной из старейших систем с открытым ключом, которые по-прежнему считаются безопасными. В отличие от RSA и ECC, опирающихся на теоретико-числовую сложность, безопасность NTRU основана на сложности поиска коротких векторов в конкретной решётке, построенной из колец многочленов. До того как постквантовая криптография стала общепринятой, NTRU была коммерциализирована и внедрена в нескольких продуктах для обеспечения безопасности.

NTRU работает в усечённом кольце многочленов Z[X]/(X^N - 1), где N — простое число. Степень многочленов в этом кольце не превышает N-1, а умножение выполняется с циклическим свёртыванием. Выбор кольца и структура многочленов с малыми коэффициентами имеют ключевое значение как для эффективности NTRU, так и для её свойств безопасности.

При генерации ключей выбираются два небольших многочлена f и g с коэффициентами из множества {-1, 0, 1}. Многочлен f должен иметь обратный элемент по модулю p (малого простого числа, обычно 3) и q (большего простого числа, обычно 2048). Открытый ключ имеет вид h = f_q^{-1} * g mod q, где f_q — обратный элемент f по модулю q. Закрытый ключ — это пара (f, g).

Чтобы зашифровать многочлен сообщения m с малыми коэффициентами, отправитель выбирает случайный небольшой маскирующий многочлен r и вычисляет c = r * h + m mod q. Шифротекст c является многочленом в том же кольце. Случайный r не позволяет двум шифротекстам одного и того же сообщения выглядеть одинаково, обеспечивая семантическую безопасность.

При расшифровании вычисляется a = f * c mod q, а коэффициенты приводятся к диапазону (-q/2, q/2]. Затем a mod p восстанавливает f_p * m mod p, а умножение на fp = f^{-1} mod p даёт m. Структура малых ошибок гарантирует, что коэффициенты f * c достаточно малы и операции mod q и mod p взаимодействуют корректно, позволяя восстановить сообщение без сбоя из-за шума.

Современная NTRU имеет два стандартизированных семейства параметров: NTRU-HPS (Хоффстейн—Пайфер—Сильверман) и NTRU-HRSS (Хулсинг—Рейнвелд—Шанк—Швабе). В NTRU-HPS используются троичные многочлены сообщений, а NTRU-HRSS применяет рандомизированное кодирование, обеспечивающее более низкую частоту ошибок расшифрования. Оба семейства стали финалистами третьего раунда PQC NIST с наборами параметров для безопасности на уровнях 128, 192 и 256 бит.

Атака за полиномиальное время на NTRU с корректно выбранными параметрами неизвестна. Лучшие атаки сводятся к поиску короткого вектора в решётке NTRU, что является экземпляром задачи приближённого SVP. Решётка NTRU имеет особую структуру с циркулянтными блоками, из-за чего атаковать её немного проще, чем случайную решётку, поэтому параметры выбираются с запасом безопасности, учитывающим эту структуру.

NTRU была активно защищена патентами компании NTRU Cryptosystems Inc. (впоследствии Security Innovation). Первоначальные патенты были поданы в 1996 и 1998 годах. Эта патентная защита в течение двух десятилетий препятствовала широкому внедрению и созданию реализаций с открытым исходным кодом. Основные патенты NTRU истекли примерно в 2017 году, после чего открытые реализации стали широко распространяться, а NTRU вошла в конкурс стандартизации PQC NIST.

NTRU была финалистом третьего раунда конкурса PQC NIST наряду с Kyber, Classic McEliece и SABER. В конечном итоге NIST выбрал Kyber (ML-KEM) в качестве основного стандарта KEM, сославшись на более простой анализ безопасности и более ясную конструкцию. NTRU не была стандартизирована, но по-прежнему остаётся жизнеспособной альтернативой, а её анализ способствовал пониманию безопасности решёточных систем.

NTRUPrime, разработанная Бернштейном, Чуэнгсатиансупом, Ланге и ван Вредендалом, намеренно устраняет структуру кольца X^N - 1 и заменяет её многочленом X^N - X - 1 простой степени. Это устраняет потенциальные уязвимости циклической структуры кольца, которые, по мнению некоторых криптоаналитиков, можно было бы использовать. NTRUPrime также была запасным кандидатом NIST PQC.

NTRU появилась раньше схем на основе LWE и не имеет формального сведения сложности в худшем случае, подобного сведению LWE Реджева. Однако NTRU быстрее при генерации ключей и имеет меньшие размеры шифротекстов, чем многие схемы LWE при сопоставимых уровнях безопасности. Компромиссом служит менее формальная основа безопасности: вместо доказательства сведения она опирается на десятилетия криптоанализа.

NTRU — новаторская криптосистема на решётках, основанная на арифметике в кольцах многочленов. При генерации ключей используются небольшие многочлены f и g, а открытый ключ имеет вид h = f^{-1}*g mod q. При шифровании используется случайное маскирование, а при расшифровании — структура f с малыми коэффициентами. NTRU не имеет формального сведения в худшем случае, но выдержала десятилетия криптоанализа. Срок действия её патентов истёк в 2017 году, и она стала финалистом третьего раунда PQC NIST.