Решёточная криптография

Решёточная криптография — это раздел криптографии, основанный на математических задачах, связанных с решётками (lattices) в многомерных евклидовых пространствах. В отличие от классических криптосистем, таких как RSA или ECC, стойкость которых основана на факторизации больших чисел или дискретном логарифмировании, решёточная криптография опирается на задачи, которые, как считается, являются труднорешаемыми даже для квантовых компьютеров. Это делает её одним из основных направлений постквантовой криптографии.

История

Предпосылки и ранние работы

Идея использования решёток в криптографии впервые была предложена в 1996 году Миклошем Айтаи (Miklós Ajtai). В своей работе «Generating Hard Instances of Lattice Problems» он показал, что существуют задачи, сложность которых в среднем случае не ниже, чем в худшем, что стало прорывом. Айтаи также предложил первую криптосистему на основе решёток, которая, однако, была неэффективной для практического использования.

Развитие в 2000-х годах

В 2005 году Одед Регев (Oded Regev) ввёл задачу обучения с ошибками (Learning With Errors, LWE), которая стала основой для большинства современных решёточных криптосистем. LWE позволила строить не только схемы шифрования, но и цифровые подписи, а также полностью гомоморфное шифрование. В 2009 году Крейг Джентри (Craig Gentry) впервые реализовал полностью гомоморфное шифрование (FHE) на основе решёток, что вызвало огромный интерес к этой области.

Современный этап

С 2010-х годов решёточная криптография активно развивается. В 2016 году Национальный институт стандартов и технологий США (NIST) начал процесс стандартизации постквантовых криптоалгоритмов, в котором решёточные схемы (например, CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON) заняли лидирующие позиции. В 2022 году NIST объявил о выборе CRYSTALS-Kyber для шифрования и CRYSTALS-Dilithium для цифровых подписей в качестве первых стандартов.

Математические основы

Решётки

Решётка (lattice) — это дискретное подмножество \( \mathbb{R}^n \), замкнутое относительно сложения и вычитания. Формально, решётка \( \Lambda \) задаётся как множество всех целочисленных линейных комбинаций \( n \) линейно независимых векторов \( \mathbf{b}_1, \ldots, \mathbf{b}_n \in \mathbb{R}^n \), называемых базисом:

\[ \Lambda = \left\{ \sum_{i=1}^n a_i \mathbf{b}_i \mid a_i \in \mathbb{Z} \right\}. \]

Решётки могут быть представлены разными базисами, и некоторые базисы (например, «короткие» и «почти ортогональные») позволяют эффективно решать задачи, в то время как другие («длинные» и «скошенные») делают их труднорешаемыми.

Ключевые задачи

Стойкость решёточной криптографии основана на следующих задачах:

• Задача нахождения кратчайшего вектора (Shortest Vector Problem, SVP): найти ненулевой вектор минимальной длины в решётке.
• Задача нахождения ближайшего вектора (Closest Vector Problem, CVP): для заданного целевого вектора найти ближайший к нему вектор решётки.
• Задача обучения с ошибками (LWE): восстановить секретный вектор \( \mathbf{s} \) по набору зашумлённых линейных уравнений \( (\mathbf{a}_i, b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i) \), где \( e_i \) — малые случайные ошибки.
• Задача кольцевого обучения с ошибками (Ring-LWE): аналог LWE, но в кольцах многочленов, что повышает эффективность.

Эти задачи считаются труднорешаемыми для классических и квантовых компьютеров при определённых параметрах (например, размерности решётки и уровне шума).

Классификация решёточных криптосистем

Схемы шифрования

• Симметричные: основаны на LWE или Ring-LWE, например, схема Регева (2005).
• Асимметричные: включают схемы с открытым ключом, такие как CRYSTALS-Kyber (выбран NIST) и FrodoKEM. Они используют механизм инкапсуляции ключей (KEM) для безопасного обмена ключами.

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

• CRYSTALS-Dilithium: основана на задаче «модульного обучения с ошибками» (Module-LWE). Обеспечивает высокую скорость и компактность подписей.
• FALCON: основана на задаче «кольцевого обучения с ошибками» (Ring-LWE) и использует технику «решёточных ловушек» (trapdoors). Подписи FALCON меньше по размеру, чем у Dilithium, но генерация ключей сложнее.

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

Решёточные решётки являются единственной известной основой для FHE, позволяющей выполнять произвольные вычисления над зашифрованными данными. Первая реализация (Gentry, 2009) использовала «идеальные решётки» (ideal lattices). Современные схемы, такие как BFV (Brakerski/Fan-Vercauteren) и CKKS (Cheon-Kim-Kim-Song), оптимизированы для практических задач, включая машинное обучение на зашифрованных данных.

Применение

Постквантовая безопасность

Основное применение решёточной криптографии — защита информации от квантовых атак. Алгоритмы, такие как CRYSTALS-Kyber и Dilithium, уже интегрируются в протоколы TLS, VPN и системы электронной подписи. В России также ведутся разработки в этой области: например, в 2023 году Центр компетенций НТИ «Технологии доверенного взаимодействия» на базе ТУСУР представил прототип постквантового криптопровайдера на основе решёток.

Гомоморфное шифрование

Решёточное FHE используется в облачных вычислениях, где требуется обработка данных без их расшифровки. Например, медицинские учреждения могут анализировать зашифрованные записи пациентов, не раскрывая конфиденциальную информацию.

Электронные голосования и блокчейн

Решёточные подписи (например, Dilithium) применяются для создания квантово-устойчивых систем электронного голосования и цифровых валют. В 2022 году компания IBM предложила интеграцию решёточных алгоритмов в блокчейн Hyperledger Fabric.

Преимущества и недостатки

Преимущества

• Квантовая устойчивость: не известны эффективные квантовые алгоритмы для решения задач SVP, LWE и их аналогов.
• Доказательная безопасность: многие решёточные схемы имеют строгие доказательства стойкости в рамках модели «случайного оракула» (random oracle model) или «стандартной модели» (standard model).
• Гибкость: решётки позволяют строить широкий спектр криптографических примитивов, включая FHE, подписи с нулевым разглашением и идентификационные схемы.

Недостатки

• Размер ключей и шифротекстов: по сравнению с классическими схемами (RSA, ECC), решёточные ключи и шифротексты значительно больше. Например, открытый ключ CRYSTALS-Kyber-512 занимает 800 байт, а закрытый — 1632 байта, что в 2–3 раза больше, чем у RSA-2048.
• Сложность реализации: правильный выбор параметров (размерность решётки, уровень шума) критичен для безопасности. Ошибки в реализации могут привести к уязвимостям.
• Производительность: хотя решёточные алгоритмы быстрее многих постквантовых альтернатив (например, на основе кодов), они всё ещё медленнее классических схем на некоторых платформах (например, на встраиваемых устройствах).

Критика и вызовы

Атаки на решёточные системы

• Атаки на основе решёточного сокращения (lattice reduction): алгоритмы, такие как LLL (Lenstra–Lenstra–Lovász) и BKZ (Block Korkin–Zolotarev), могут находить короткие векторы в решётках малой размерности. Для современных схем размерность выбирается достаточно большой (например, 512–1024), чтобы такие атаки были неэффективны.
• Атаки по сторонним каналам: как и другие криптосистемы, решёточные схемы уязвимы к анализу времени выполнения, энергопотребления и электромагнитного излучения. В 2023 году исследователи из Университета Кюсю продемонстрировали атаку по времени на реализацию CRYSTALS-Kyber в библиотеке liboqs.
• Квантовые атаки: хотя квантовые компьютеры не могут решить SVP или LWE за полиномиальное время, существуют квантовые алгоритмы, ускоряющие некоторые подзадачи (например, алгоритм Гровера для поиска в решётках). Это требует увеличения параметров безопасности.

Споры о стандартизации

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

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

• Термин «решётка» (lattice) в криптографии не следует путать с «решёткой» в теории групп (lattice) — это разные понятия, хотя и связанные.
• В 2020 году исследователи из Массачусетского технологического института (MIT) показали, что решёточные криптосистемы могут быть использованы для создания «квантово-устойчивых» блокчейнов, устойчивых к атакам с использованием квантовых компьютеров.
• В 2023 году компания Google объявила о тестировании решёточных алгоритмов в своём браузере Chrome для защиты от будущих квантовых угроз.

Источники

• Ajtai, M. (1996). «Generating Hard Instances of Lattice Problems». STOC '96.
• Regev, O. (2005). «On Lattices, Learning with Errors, Random Linear Codes, and Cryptography». STOC '05.
• Gentry, C. (2009). «Fully Homomorphic Encryption Using Ideal Lattices». STOC '09.
• NIST (2022). «Post-Quantum Cryptography: Selected Algorithms».
• Bernstein, D. J., & Lange, T. (2017). «Post-Quantum Cryptography». Nature.
• Chen, L., et al. (2016). «Report on Post-Quantum Cryptography». NIST IR 8105.