Криптография на решётках

Криптография на решётках — это раздел постквантовой криптографии, в котором криптографические примитивы (шифры, схемы подписи, протоколы) строятся на основе математических задач, связанных с решётками (lattices) в многомерных евклидовых пространствах. Основой стойкости таких систем является предполагаемая вычислительная сложность решения задач, таких как поиск кратчайшего вектора (SVP) или задача обучения с ошибками (LWE), которые, как считается, не имеют эффективного решения даже на квантовых компьютерах.

История

Ранние работы

Идея использования решёток в криптографии восходит к работам 1980-х годов. В 1982 году Ласло Ловас и Хендрик Ленстра разработали алгоритм LLL (по первым буквам фамилий авторов), который позволял эффективно находить короткие векторы в решётках малой размерности. Этот алгоритм стал инструментом для атак на некоторые криптосистемы, но одновременно показал, что в высоких размерностях задача остаётся сложной.

Первые криптосистемы

В 1996 году Миклош Айтай предложил первую криптосистему на решётках, основанную на задаче о кратчайшем векторе (SVP). Его работа показала, что взлом такой системы эквивалентен решению NP-трудной задачи в худшем случае. В 1997 году Одед Гольдрейх, Шафи Гольдвассер и Шай Халеви представили криптосистему GGH, основанную на задаче о ближайшем векторе (CVP). Однако GGH была уязвима для некоторых атак, и её практическое применение было ограничено.

Прорыв: задача LWE

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

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

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

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

Решётки

Решётка — это дискретное подмножество \( \mathbb{R}^n \), состоящее из всех целочисленных линейных комбинаций \( n \) линейно независимых векторов \( \mathbf{b}_1, \dots, \mathbf{b}_n \): \[ L = \left\{ \sum_{i=1}^n a_i \mathbf{b}_i \mid a_i \in \mathbb{Z} \right\}. \] Векторы \( \mathbf{b}_i \) образуют базис решётки. Решётка может быть представлена разными базисами, и задача нахождения «короткого» базиса (с малыми по длине векторами) является сложной.

Основные задачи

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

Классификация криптосистем

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

• Криптосистема Райгеля (2005): основана на LWE, обеспечивает семантическую стойкость. Шифротекст — это пара \( (\mathbf{a}, b) \), где \( b = \langle \mathbf{a}, \mathbf{s} \rangle + e + m \cdot q/2 \), \( m \) — бит сообщения.
• CRYSTALS-Kyber: финалист NIST, основан на модульном LWE (Module-LWE). Использует небольшие размерности (например, \( n=256 \)) и кольца многочленов. Обеспечивает высокую скорость и компактность ключей.
• FrodoKEM: альтернатива, основанная на стандартном LWE без колец, что даёт более консервативную стойкость, но больший размер ключей.

Схемы цифровой подписи

• CRYSTALS-Dilithium: основан на задаче Module-LWE и Module-SIS (Short Integer Solution). Подпись состоит из нескольких векторов и проверяется через вычисление хеша. Утверждён NIST как FIPS 204.
• FALCON: основан на кольцевом LWE и использует решётки НТРУ (NTRU). Отличается очень компактными подписями, но сложнее в реализации.
• SPHINCS+: хотя не основан на решётках, иногда упоминается в контексте постквантовой криптографии; использует хеш-функции.

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

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

Применение

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

Основное применение криптографии на решётках — защита от квантовых компьютеров. Алгоритмы Шора и Гровера делают уязвимыми RSA, ECC и DSA, но задачи на решётках остаются сложными для квантовых алгоритмов. Поэтому решёточные схемы рассматриваются как замена существующим криптосистемам.

Интернет и связь

• Протокол TLS: в 2024 году началось внедрение CRYSTALS-Kyber в качестве дополнительного алгоритма для обмена ключами в TLS 1.3.
• VPN и SSH: поддержка постквантовых алгоритмов добавляется в OpenVPN, WireGuard и OpenSSH.
• Электронная подпись: CRYSTALS-Dilithium используется в государственных системах электронного документооборота в ряде стран, включая Россию (в рамках экспериментов по постквантовой криптографии).

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

Криптография на решётках позволяет обрабатывать зашифрованные данные без расшифровки. Это применяется в:

• облачных вычислениях (анализ данных, машинное обучение);
• медицинских исследованиях (обработка конфиденциальных данных пациентов);
• финансовых системах (безопасные вычисления с транзакциями).

Квантово-устойчивые блокчейны

Некоторые блокчейн-проекты, такие как Solana и Algorand, рассматривают переход на решёточные подписи для защиты от квантовых атак. В 2023 году был запущен тестовый блокчейн на основе CRYSTALS-Dilithium.

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

Размер ключей и шифротекстов

Решёточные схемы имеют значительно большие размеры ключей и шифротекстов по сравнению с RSA и ECC. Например, открытый ключ CRYSTALS-Kyber-512 занимает 800 байт, а закрытый — 1632 байта, что в несколько раз больше, чем у ECC. Для схем подписи (Dilithium) размер подписи может достигать 2–3 КБ. Это создаёт проблемы для устройств с ограниченной памятью (IoT, смарт-карты).

Производительность

Хотя решёточные алгоритмы быстрее многих других постквантовых схем (например, на основе кодов), они всё же медленнее традиционных на некоторых платформах. На микроконтроллерах и мобильных устройствах время вычислений может быть критичным.

Атаки на реализацию

Как и любая криптография, решёточные схемы уязвимы для атак по побочным каналам (side-channel attacks): анализ времени выполнения, потребления энергии, электромагнитного излучения. Требуются дополнительные меры защиты (например, постоянное время выполнения).

Неопределённость стойкости

Хотя задачи на решётках считаются сложными, не существует строгого доказательства, что они не могут быть решены за полиномиальное время на квантовом компьютере. Прогресс в квантовых алгоритмах (например, алгоритм Ллойда-Шора для решёток) может изменить ситуацию.

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

• В 2018 году учёные из Массачусетского технологического института (MIT) продемонстрировали атаку на решёточные схемы с использованием квантового компьютера IBM, но она была ограничена размерностью 2–3, что не имеет практического значения.
• Криптография на решётках лежит в основе протокола «обфускации» (indistinguishability obfuscation), который считается «святым Граалем» криптографии.
• В России в 2023 году был утверждён национальный стандарт ГОСТ Р 34.10-2023, который включает постквантовые алгоритмы, в том числе на основе решёток (схема подписи «Кристалл»).

Источники

• Regev O. «On lattices, learning with errors, random linear codes, and cryptography» (2005).
• NIST. «Post-Quantum Cryptography: Selected Algorithms 2022» (2022).
• Bernstein D. J., Buchmann J., Dahmen E. «Post-Quantum Cryptography» (2009).
• Peikert C. «A Decade of Lattice Cryptography» (2016).
• ГОСТ Р 34.10-2023 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».