Обучение с ошибками: сложная задача

Задача обучения с ошибками (LWE) была предложена Одедом Регевом в 2005 году как основа постквантовой криптографии. Имея случайную матрицу A над Z_q и вектор b = As + e, необходимо найти секретный вектор s. Вектор e представляет собой небольшую ошибку, выбранную из дискретного гауссовского распределения, что делает задачу вычислительно неразрешимой.

В задаче LWE A — случайная матрица размера m x n, равномерно выбранная над Z_q, где q — простой модуль. Секрет s — вектор размерности n, а e — небольшой вектор ошибок, элементы которого выбираются из узкого гауссового распределения. Даже знание структуры A не помогает противнику отличить b от равномерно случайного вектора.

Существуют две стандартные формулировки LWE. В поисковой задаче LWE требуется восстановить секрет s по множеству образцов (A, b). В десизионной задаче LWE требуется отличить образцы (A, As + e) от равномерно случайных пар (A, u). Эти две формулировки полиномиально эквивалентны: алгоритм, решающий одну из них, можно преобразовать в алгоритм для решения другой.

Слагаемое ошибки в LWE выбирается из дискретного гауссового распределения над целыми числами, параметризованного стандартным отклонением sigma. Небольшие значения sigma гарантируют, что e короток по сравнению с q, благодаря чему b выглядит почти как As mod q. Если бы sigma равнялось нулю, ошибки не было бы, и систему можно было бы решить методом исключения Гаусса, поэтому ошибка необходима для обеспечения сложности.

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

В отличие от RSA и криптографии на эллиптических кривых, неизвестно ни одного квантового алгоритма, обеспечивающего экспоненциальное ускорение атак на LWE. Алгоритм Гровера даёт не более чем квадратичное ускорение, а лучшие квантовые алгоритмы для решёток — варианты BKZ — не взламывают LWE при корректно выбранных параметрах. Поэтому LWE служит надёжной основой постквантовой безопасности.

Безопасность LWE определяется тремя параметрами: размерностью n (длиной секрета), модулем q и стандартным отклонением ошибки sigma. Большие значения n и меньшее отношение q/sigma повышают безопасность. Для постквантовой безопасности на уровне 128 бит обычно используются значения n = 1024, q около 12289 и sigma около 3.2. Для оценки конкретного уровня безопасности применяется инструмент оценки решёток Альбрехта и др.

Задача короткого целочисленного решения (SIS) — это связанное с решётками предположение о сложности, используемое для подписей. По случайной матрице A над Z_q требуется найти короткий ненулевой вектор x такой, что Ax = 0 mod q. SIS лежит в основе хеш-функций и схем подписей в решёточной криптографии, дополняя LWE, на котором основаны шифрование и инкапсуляция ключей.

Простая схема шифрования LWE работает следующим образом: открытый ключ имеет вид (A, b = As + e), а закрытым ключом служит s. Чтобы зашифровать бит m, отправитель вычисляет (u, v) = (A^T r, b^T r + m * floor(q/2)) для случайного двоичного вектора r. При расшифровании вычисляется v - s^T u, после чего результат округляется для восстановления m. Эта схема обеспечивает безопасность IND-CPA при предположении сложности LWE.

LWE позволила создать широкий спектр криптографических конструкций, выходящих за рамки базового шифрования. К ним относятся полностью гомоморфное шифрование (FHE), шифрование на основе идентичности (IBE), шифрование на основе атрибутов (ABE) и протоколы обмена ключами. CRYSTALS-Kyber (теперь ML-KEM, стандартизированный как FIPS 203) — наиболее широко применяемая на практике схема на основе LWE.

Криптография на основе LWE уже внедряется в рабочие системы. Google и Cloudflare проводили эксперименты с TLS, используя Kyber, в 2018–2020 годах. В 2024 году Chrome и Firefox добавили поддержку ML-KEM-768 в гибридных рукопожатиях TLS. Протокол Signal добавил постквантовый уровень (PQXDH), использующий ML-KEM-1024 для прямой секретности и защищающий конфиденциальность долгосрочных сообщений от будущих квантовых компьютеров.

Какое утверждение лучше всего описывает гарантию сложности задачи LWE?

LWE — одно из наиболее тщательно изученных предположений о постквантовой сложности, подкреплённое сильным сведением в худшем случае от задач на решётках. Три её параметра (n, q, sigma) определяют компромисс между безопасностью и производительностью. LWE устойчива к квантовым атакам и лежит в основе схем, стандартизированных NIST. Понимание LWE открывает путь ко всей современной решёточной криптографии, включая ML-KEM и ML-DSA.