Обучение с ошибками (LWE): основа

Обучение с ошибками (LWE), предложенное Regev в 2005 году: по множеству зашумлённых линейных уравнений над Z_q требуется найти секретный вектор s. Шум e мал, но не позволяет применить метод исключения Гаусса. Без шума система решается легко; даже при очень малом шуме она становится вычислительно трудной.

Секрет s ∈ Z_q^n. Атакующий получает образцы (a_i, b_i), где a_i ∈ Z_q^n — случайный вектор, b_i = + e_i mod q, а e_i — малый шум из распределения χ (например, гауссовского с σ = √n). Задача: найти s, имея полиномиальное число образцов.

Без шума: b_i = mod q. Метод исключения Гаусса восстанавливает s за O(n^3). При наличии шума: даже одно ошибочное уравнение нарушает процесс исключения. Шум достаточно мал, чтобы расшифрование работало с помощью ключа, но достаточно велик, чтобы препятствовать криптоанализу.

Regev доказал, что LWE сводится к задачам о решётках в наихудшем случае (SIVP, GapSVP) с помощью квантовой редукции. Это означает: если LWE удастся взломать, будут решены многие трудные задачи о решётках, однако ни одного квантового алгоритма для задач о решётках пока не известно. LWE обладает постквантовой защищённостью.

Кольцевой LWE (RLWE) заменяет Z_q^n кольцом Z_q[x]/(f(x)) для циклотомического многочлена f. Один образец RLWE кодирует n уравнений, что значительно повышает эффективность. RLWE лежит в основе Kyber (KEM), Dilithium (подпись) и схем HE BFV/BGV/CKKS.

Безопасность зависит от следующих параметров: n (размерность, обычно 512–2048), q (модуль, 1024–2^60), σ (стандартное отклонение шума). Чем больше n и меньше отношение σ/q, тем труднее задача. Постквантовые стандарты NIST используют n=256 (размерность модуля) и k модулей (k=2,3,4).

Открытый ключ: (A, b=As+e). Для шифрования бита m: выберите случайный r и вычислите шифротекст (u=A^T r, v = b^T r + m*q/2). Расшифрование: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Округлите до ближайшего m. Шум e не позволяет раскрыть m по шифротексту во время шифрования.

Задача различения LWE: отличить (a, As+e) от (a, u), где u равномерно распределён случайным образом. При условии трудности LWE эти распределения вычислительно неразличимы. Это основа семантической безопасности: для атакующих без секретного ключа шифротексты выглядят как случайный шум.

Лучшие из известных атак используют BKZ (блочную редукцию решётки Коркина—Золотарёва). Сложность субэкспоненциальна, но не полиномиальна. Для BKZ-β требуется 2^{0.292β} операций. Для LWE-512 безопасность против BKZ составляет примерно 128 бит. Квантовое ускорение для BKZ неизвестно.

Модульный LWE (используемый в Kyber) — это RLWE над модулями ранга k. Он обеспечивает гибкость: k=2 для 512-битной безопасности, k=3 для 768-битной, k=4 для 1024-битной. Безопасность и производительность масштабируются с k. NIST выбрал Kyber (переименованный в ML-KEM) в качестве стандарта PQC.

Безопасность RSA/ECC основана на факторизации целых чисел и дискретном логарифмировании и уязвима к квантовым атакам с использованием алгоритма Шора. Безопасность LWE основана на трудных задачах о решётках, для которых не известно квантового ускорения. Размер ключей: ключи LWE занимают около 1 KB, а RSA-2048 — 256 байт. LWE использует больше памяти, но устойчив к квантовым атакам.

Почему LWE остаётся трудной для решения даже при наличии большого числа образцов?

LWE: поиск секретного s по зашумлённым линейным уравнениям — задача, трудная для квантовых компьютеров. RLWE использует кольца многочленов для повышения эффективности. LWE и RLWE лежат в основе Kyber, Dilithium и схем HE. Далее: схемы HE BGV и BFV для операций над целыми числами.