Learning With Errors¶

Learning With Errors (LWE, обучение с ошибками) — это задача теории вычислительной сложности, лежащая в основе многих современных криптографических систем с постквантовой защитой. Впервые формально описана Одедом Регевым в 2005 году. Задача заключается в восстановлении секретного вектора (или матрицы) по набору зашумлённых линейных уравнений над конечным полем или кольцом. Стойкость LWE основана на предполагаемой сложности решения некоторых задач теории решёток (lattice problems), в частности, задачи о кратчайшем векторе (SVP) и задачи о ближайшем векторе (CVP) в худшем случае. LWE считается одной из наиболее перспективных основ для построения криптографии, устойчивой к атакам с использованием квантовых компьютеров.

¶История

Задача Learning With Errors была введена израильским учёным Одедом Регевым в 2005 году в работе «On lattices, learning with errors, random linear codes, and cryptography». Регев показал, что решение LWE в среднем случае не проще, чем решение некоторых задач теории решёток в худшем случае, что обеспечивает теоретическую обоснованность стойкости. До этого, в 1996 году, Миклош Айтай и Синтия Дворк предложили первую криптосистему на основе решёток, но LWE стала более универсальным и удобным инструментом.

В 2009 году Крейг Джентри предложил первую полностью гомоморфную схему шифрования (FHE), основанную на идеях, близких к LWE. В 2010-х годах LWE-подобные задачи (Ring-LWE, Module-LWE) стали основой для стандартизации постквантовой криптографии в США (NIST). В 2022 году NIST выбрал алгоритмы CRYSTALS-Kyber (на основе Module-LWE) и CRYSTALS-Dilithium (на основе Module-LWE) для стандартизации в качестве схем шифрования и цифровой подписи соответственно.

¶Формальное определение

Пусть \( n \) — размерность секрета, \( q \) — модуль (обычно простое число), \( \chi \) — распределение ошибок (часто дискретное гауссово). Секретный вектор \( \mathbf{s} \in \mathbb{Z}_q^n \) неизвестен. Оракул выдаёт пары \( (\mathbf{a}_i, b_i) \), где \( \mathbf{a}_i \) — равномерно случайный вектор из \( \mathbb{Z}_q^n \), а \( b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod{q} \), где \( e_i \) — малая ошибка, взятая из распределения \( \chi \). Задача: по набору \( m \) таких пар восстановить \( \mathbf{s} \).

Различают два варианта:

• Search-LWE: найти сам секретный вектор \( \mathbf{s} \).
• Decision-LWE: отличить пары \( (\mathbf{a}_i, b_i) \), полученные по описанной схеме, от равномерно случайных пар \( (\mathbf{a}_i, u_i) \), где \( u_i \) — равномерно случайное число из \( \mathbb{Z}_q \).

Доказано, что при определённых параметрах Search-LWE и Decision-LWE эквивалентны по сложности.

¶Разновидности LWE

¶Ring-LWE (RLWE)

Ring-LWE — это вариант LWE, работающий в кольце многочленов \( R_q = \mathbb{Z}_q[x]/(f(x)) \), где \( f(x) \) — круговой многочлен (часто \( x^n + 1 \)). Вместо векторов используются многочлены, что позволяет значительно повысить эффективность за счёт использования быстрых преобразований Фурье (FFT). RLWE лежит в основе многих практических схем, таких как NewHope (не был стандартизирован NIST) и CRYSTALS-Kyber (использует Module-LWE, обобщение RLWE).

¶Module-LWE (MLWE)

Module-LWE — это обобщение, в котором секрет и ошибки являются матрицами или векторами над кольцом \( R_q \). MLWE объединяет гибкость LWE и эффективность RLWE. Именно MLWE используется в алгоритмах CRYSTALS-Kyber и CRYSTALS-Dilithium, выбранных NIST для стандартизации.

¶Learning With Rounding (LWR)

LWR — детерминированный вариант LWE, где вместо добавления случайной ошибки используется округление (rounding) значений. LWR проще в реализации, но требует других доказательств стойкости.

¶Применение в криптографии

¶Постквантовое шифрование

LWE является основой для нескольких схем шифрования с открытым ключом, устойчивых к квантовым атакам. Наиболее известные:

• CRYSTALS-Kyber (стандартизирован NIST в 2022 году как ML-KEM) — схема инкапсуляции ключей (KEM) на основе Module-LWE.
• FrodoKEM — схема на основе классической LWE (без кольцевых структур), обеспечивающая консервативный уровень безопасности.
• NewHope — схема на основе Ring-LWE, была финалистом конкурса NIST, но не была выбрана.

¶Цифровые подписи

LWE также используется для построения цифровых подписей:

• CRYSTALS-Dilithium (стандартизирован NIST как ML-DSA) — на основе Module-LWE и Module-LWR.
• FALCON — на основе кольцевых решёток (Ring-LWE), также стандартизирован NIST.

¶Полностью гомоморфное шифрование (FHE)

LWE является ключевым строительным блоком для FHE. Первая схема Крейга Джентри (2009) использовала идеи, близкие к LWE. Современные FHE-схемы (BFV, BGV, CKKS) основаны на Ring-LWE и позволяют выполнять произвольные вычисления над зашифрованными данными.

¶Протоколы с нулевым разглашением (ZKP)

LWE используется для построения эффективных доказательств с нулевым разглашением, в том числе для постквантовых систем.

¶Стойкость и атаки

Стойкость LWE основана на предположении, что задача о кратчайшем векторе (SVP) в решётках не имеет полиномиального алгоритма решения ни на классических, ни на квантовых компьютерах. Наиболее известные атаки на LWE включают:

• Решёточные атаки (например, алгоритм BKZ с просеиванием или перечислением).
• Атаки на основе линейного программирования (например, метод Арора-Ги).
• Атаки на основе квантовых алгоритмов (алгоритм Гровера может ускорить перебор, но не даёт экспоненциального ускорения для LWE).

На практике для обеспечения безопасности выбирают параметры, при которых известные атаки требуют не менее \( 2^{128} \) или \( 2^{256} \) операций.

¶Критика и ограничения

• Размер ключей и шифротекстов: LWE-схемы обычно имеют большие размеры ключей по сравнению с классическими (RSA, ECC). Например, открытый ключ Kyber-512 занимает около 800 байт, что больше, чем у RSA-2048 (256 байт), но меньше, чем у некоторых других постквантовых схем.
• Сложность реализации: Для эффективной работы требуются операции с большими целыми числами и быстрые преобразования, что усложняет реализацию на встраиваемых устройствах.
• Неопределённость будущих атак: Хотя LWE считается стойкой, не исключено, что в будущем будут найдены более эффективные алгоритмы решения задач теории решёток, что потребует пересмотра параметров.

¶Интересные факты

• Одед Регев получил премию Гёделя в 2018 году за работу по LWE.
• В 2022 году NIST объявил о стандартизации CRYSTALS-Kyber и CRYSTALS-Dilithium, что стало важным шагом к внедрению постквантовой криптографии.
• LWE используется не только в криптографии, но и в машинном обучении (например, в обучении с учителем на зашумлённых данных).

¶Источники

• Regev, Oded. «On lattices, learning with errors, random linear codes, and cryptography.» Journal of the ACM, 2009.
• Gentry, Craig. «Fully homomorphic encryption using ideal lattices.» STOC, 2009.
• NIST. «Post-Quantum Cryptography: Selected Algorithms 2022.» National Institute of Standards and Technology, 2022.
• Lyubashevsky, Vadim, et al. «On ideal lattices and learning with errors over rings.» EUROCRYPT, 2010.