Ring-LWE и решетки модулей

Стандартная LWE требует умножения больших матриц на векторы, что приводит к большим размерам ключей. Ring-LWE, предложенная Любашевским, Пейкертом и Реджевом в 2010 году, заменяет векторы и матрицы многочленами в кольце R_q = Z_q[X]/(f(X)). Такая структурированная среда позволяет значительно уменьшить размеры ключей и ускорить арифметические операции, благодаря чему Ring-LWE стала практической основой реальной решёточной криптографии.

В Ring-LWE обычно используется многочлен f(X) = X^n + 1, где n — степень двойки. Это 2n-й циклотомический многочлен. Он выбран потому, что неприводим над Z, обеспечивает хорошие алгебраические свойства кольца R_q и позволяет применять теоретико-числовое преобразование (NTT) для эффективного умножения. Циклотомические кольца тщательно исследованы и считаются безопасными.

В Ring-LWE секрет s является многочленом в R_q, а образцы имеют вид (a, b = a*s + e), где a — равномерно случайный элемент кольца, а e — небольшой многочлен ошибок. Противник видит множество таких образцов и должен восстановить s или отличить их от равномерно случайных. Сложность основана на предположении Ring-LWE, для которого существует сведение от задач худшего случая на идеальных решётках.

Ring-LWE сложнее для противника, но её сведение безопасности немного отличается от сведения обычной LWE. Оно выполняется от задач худшего случая на идеальных решётках (ideal-SVP), а не на произвольных решётках. Дополнительная структура идеальных решёток в принципе может сделать их более лёгкими для атак, и это активно исследуется. Практической атаки, использующей эту структуру, неизвестно.

Module-LWE (M-LWE) обобщает LWE и Ring-LWE, работая с матрицей k x k элементов кольца, а не с одним элементом кольца или большой матрицей целых чисел. При k = 1 она сводится к Ring-LWE, а с ростом k приближается к стандартной LWE. Этот настраиваемый параметр k позволяет уравновешивать уверенность в безопасности и производительность.

CRYSTALS-Kyber (теперь ML-KEM, FIPS 203) основана на Module-LWE с матрицей ранга k над R_q. Параметр k напрямую определяет уровень безопасности: k=2 соответствует безопасности 128 бит (ML-KEM-512), k=3 — 192 битам (ML-KEM-768), а k=4 — 256 битам (ML-KEM-1024). Модульная структура позволяет использовать единую кодовую базу, изменяя k для масштабирования безопасности.

Умножение многочленов в R_q = Z_q[X]/(X^n + 1) является узким местом производительности. Теоретико-числовое преобразование (NTT) — это дискретное преобразование Фурье над Z_q, переводящее многочлены в представление значениями, где умножение становится поточечным. При выборе q, допускающем применение NTT, умножение многочленов занимает время O(n log n) вместо O(n^2), что является критически важной оптимизацией в ML-KEM и ML-DSA.

Для NTT требуется, чтобы q было простым числом и выполнялось q = 1 mod 2n, благодаря чему Z_q содержит примитивный корень 2n-й степени из единицы. Для ML-KEM при n = 256 число q = 3329 удовлетворяет этому требованию. NTT над Z_3329 чрезвычайно быстро работает на современном оборудовании с инструкциями SIMD, что позволяет выполнять тысячи операций ML-KEM в секунду на обычных процессорах.

Кольцевой LWE и модульный LWE значительно уменьшают размеры ключей по сравнению со стандартным LWE. Открытый ключ стандартного LWE со стойкостью 128 бит может занимать 1 MB; кольцевой LWE уменьшает этот размер примерно до 800 байт, а модульный LWE (ML-KEM-768) обеспечивает открытый ключ размером 1184 байта при постквантовой стойкости 192 бита. Такая компактность делает решёточные схемы пригодными для практического применения в TLS и во встраиваемых системах.

Некоторые криптографы опасаются, что дополнительная алгебраическая структура циклотомических колец может сделать возможными атаки, неприменимые к обычному LWE. В 2024 году Элиас Рокицки и его коллеги опубликовали анализ 2n-го циклотомического многочлена. Они не обнаружили практически применимых атак, но подчеркнули важность дальнейшего изучения. В рамках процесса NIST PQC этот риск учитывался, и модульный LWE был выбран в том числе для уменьшения зависимости от какой-либо одной структуры кольца.

Помимо Kyber, кольцевой LWE лежит в основе CRYSTALS-Dilithium (ML-DSA) — стандартизованной NIST схемы цифровой подписи. Библиотека SEAL от Microsoft обеспечивает гомоморфное шифрование с помощью кольцевого LWE. Криптографическая библиотека Tink от Google включает поддержку ML-KEM. Кольцевой LWE прошёл путь от теоретической конструкции до промышленного внедрения за удивительно короткий срок благодаря процессу стандартизации NIST.

Каково основное преимущество кольцевого LWE по сравнению со стандартным LWE?

Кольцевой LWE переносит LWE в кольцо многочленов R_q = Z_q[X]/(X^n+1), значительно уменьшая размеры ключей и обеспечивая быстрые вычисления на основе NTT. Модульный LWE обобщает этот подход с помощью структуры ранга k и лежит в основе ML-KEM (FIPS 203) и ML-DSA (FIPS 204). Простое число q = 3329, удобное для NTT, обеспечивает эффективную реализацию. Стойкость опирается на трудность решения задач на идеальных и модульных решётках.