Курс «Квантовые вычисления». Глава 13. Постквантовая криптография

Курс «Квантовые вычисления»

Цели главы. Разобрать математику замены: решётки и LWE (стандарты ML-KEM и ML-DSA), хеш-подписи (SLH-DSA и учебная схема Лампорта), коды (выбранный для будущего стандарта HQC). Отдельно — история падения SIKE и практический смысл разнообразия. К концу главы аббревиатуры PQC должны превратиться в понятные конструкции, а статус «стандарт», «выбран для стандартизации» и «исследовательский кандидат» — перестать смешиваться.

13.1. Техническое задание на замену

Из глав 7 и 12 следует, чем провинилась старая асимметрика: факторизация и дискретный логарифм — задачи со скрытой периодической структурой, которую вскрывает квантовое преобразование Фурье. Требования к новой математике:

1. отсутствие известных эффективных классических и квантовых атак при чётко заданных параметрах и модели безопасности; одной лишь непохожести на задачу Шора недостаточно;
2. работа на обычном классическом железе (PQC — это софт, никакой квантовой аппаратуры);
3. практичные размеры ключей, подписей и скорость;
4. зрелость криптоанализа: задачу должны были всерьёз ломать годами.

NIST объявил открытый процесс в 2016 году, получил 82 комплекта предложений в 2017-м и после нескольких раундов выпустил первые три стандарта в 2024-м. Это не турнир с окончательным доказательством победителя: криптоанализ, дополнительные подписи и резервный KEM продолжаются, а параметры и реализации требуют постоянной проверки.

13.2. Решётки и задача LWE

Решётка — множество всех целочисленных комбинаций линейно независимых базисных векторов: дискретная «кристаллическая сетка» точек в евклидовом пространстве. Среди базовых вычислительных задач — найти короткий ненулевой вектор (SVP) или близкую к заданной точку (CVP), с точно указанным коэффициентом приближения. Для криптографических размерностей известные атаки требуют быстро растущих ресурсов, но фраза «SVP экспоненциальна» без варианта задачи, точности и модели вычислений неполна. Параметры стандартов выбраны по лучшим известным классическим и квантовым атакам и должны пересматриваться по мере прогресса криптоанализа.

Рабочая лошадка стандартов — задача обучения с ошибками (Learning With Errors, Регев, 2005). Дан секретный вектор s из n чисел по модулю q. Противнику выдаются уравнения с шумом: случайные векторы a_i и значения b_i = ⟨a_i, s⟩ + e_i (mod q), где e_i — малые случайные ошибки. Восстановить s.

Без шума достаточно линейной алгебры над ℤ_q. При шуме правая часть уже не задаёт точную линейную систему: исключение преобразует вместе с уравнениями неизвестные ошибки, и обычный метод Гаусса не выдаёт s. Игрушечный пример (q = 17, n = 2, s = (3, 5)) разобран в упражнении 1. Теоретический фундамент LWE — редукции от худшего случая к среднему. В исходном результате Регев показал квантовую редукцию от определённых приближённых задач на решётках в худшем случае к решению средней LWE при согласованных параметрах; позднее появились другие варианты и редукции. Это сильное свидетельство, но не доказательство абсолютной стойкости конкретной схемы, не запрет всех слабых реализаций или ключей и не утверждение, что любой вариант LWE эквивалентен точной SVP.

Практичные схемы используют Module-LWE: линейная алгебра идёт над модулями, построенными из колец многочленов. Структура ускоряет умножение и уменьшает ключи до килобайт, но одновременно вводит более специальное предположение, которое тоже анализируют отдельно. Отсюда «ML» в ML-KEM — Module-Lattice; в ML-DSA та же приставка указывает на модульно-решёточное основание.

13.3. ML-KEM: постквантовый обмен ключами

Современный примитив обмена — не «шифрование», а KEM (механизм инкапсуляции ключа), три операции: KeyGen → пара (pk, sk); Encaps(pk) → (шифртекст c, общий секрет K); Decaps(sk, c) → K. Обе стороны получают общий K — дальше работает симметрика.

Идея внутреннего шифрования ML-KEM (бывший CRYSTALS-Kyber) на пальцах: открытый ключ содержит модульно-LWE-отношение t = As + e; инкапсулятор выбирает краткий временный секрет и шумы, сжимает полученные многочлены и кодирует случайное 32-байтное значение. Владелец s снимает основную линейную часть и восстанавливает значение несмотря на малый шум. Полный KEM не просто «шифрует готовый K»: он хеширует случайное значение и шифртекст, а при декапсуляции повторно проверяет корректность и использует неявный отказ, чтобы получить стойкость к выбранному шифртексту.

FIPS 203 задаёт ML-KEM-512/768/1024 — категории NIST 1, 3 и 5, которые сравнивают стоимость атак с эталонными атаками на AES и хеши, но не сводят к одному числу «бит стойкости». NIST рекомендует ML-KEM-768 как набор по умолчанию. Его сырой ключ инкапсуляции занимает 1184 байта, шифртекст — 1088, общий секрет — 32; сериализация PEM/DER добавляет оболочку. В гибридной группе TLS клиентский key_share содержит ещё 32 байта X25519 и потому увеличивает ClientHello примерно на 1184 байта относительно одного X25519, а ответ сервера — примерно на 1088. Скорость зависит от процессора и реализации: решёточная арифметика часто конкурентоспособна, но универсального «быстрее ECDH» нет.

13.4. ML-DSA: постквантовые подписи

ML-DSA (бывший CRYSTALS-Dilithium) — подпись на модульно-решёточной математике, построенная как преобразование Фиата–Шамира с отказами: хеш сообщения и обязательства образует вызов, а подписант отбрасывает попытки, чьё распределение могло бы выдать лишнюю информацию о секрете. FIPS 204 задаёт ML-DSA-44/65/87. У ML-DSA-65 сырой открытый ключ занимает 1952 байта, подпись — 3309 байт; для сравнения, сырая ECDSA P-256-подпись содержит два 32-байтных числа, а DER-кодирование обычно добавляет несколько байтов. Сертификатные цепочки с несколькими ключами и подписями заметно тяжелеют, поэтому исследуются более компактные подписи, включая будущий FN-DSA. Производительность надо измерять на целевой платформе: генерация ключа, подписание и проверка имеют разные профили.

13.5. Хеш-подписи: криптография на минимальных допущениях

Теперь конструкция, которую стоит разобрать до винтика, — она элементарна и красива. Одноразовая подпись Лампорта (1979) для сообщения из k бит (подписываем его хеш, k = 256):

• Секретный ключ: 2k случайных строк — пара (x_i,0, x_i,1) на каждую позицию i.
• Открытый ключ: их хеши — пары (H(x_i,0), H(x_i,1)).
• Подпись сообщения с битами b₁…b_k: раскрыть по одной строке на позицию — x_i,bi.
• Проверка: хеш каждой раскрытой строки должен совпасть с соответствующей половиной открытого ключа.

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

Путь к многоразовости: сгенерировать много одноразовых пар и связать их деревом Меркла — открытым ключом всей конструкции служит один корневой хеш, подпись включает путь аутентификации от листа к корню. Так устроены стандартизованные схемы с состоянием XMSS и LMS: они требуют надёжно помнить использованные листья, а откат счётчика из резервной копии может повторно использовать одноразовый ключ. SLH-DSA (на основе SPHINCS+) вместо внешнего счётчика использует FORS и многоуровневое гипердерево; безопасность учитывает возможные совпадения выбранных индексов, а не объявляет их невозможными. FIPS 205 содержит 12 наборов: подписи от 7856 байт у SLH-DSA-*-128s до 49 856 байт у *-256f; «s» означает меньшую подпись, «f» — более быстрое подписание. Большие подписи и вычислительная цена делают SLH-DSA естественным кандидатом для редких долгоживущих подписей, но конкретную нишу определяет профиль системы.

13.6. Коды: McEliece и HQC

Третье основание — коды, исправляющие ошибки. В общей картине открытый ключ описывает скрыто структурированный код, а шифртекст содержит намеренно добавленную ошибку; владелец секрета декодирует её эффективно. Общая задача синдромного декодирования NP-полна, но это само по себе не доказывает стойкость конкретного распределения ключей и параметров. Патриарх направления — McEliece (1978): десятилетия криптоанализа дают высокий уровень доверия, а цена классических вариантов — открытые ключи порядка сотен килобайт или мегабайта. В марте 2025 года NIST выбрал HQC для будущей стандартизации как второй KEM с независимым от решёток основанием; по состоянию на август 2026 года FIPS для HQC ещё готовится. Называть HQC уже стандартизованным нельзя.

13.7. Урок SIKE: почему основания дублируют

Поучительнейшая история конкурса. SIKE — схема на изогениях суперсингулярных эллиптических кривых — дошла до дополнительного четвёртого раунда: компактные ключи, красивая математика, годы анализа. Летом 2022 года Воутер Кастрик и Томас Декрю опубликовали классическую атаку восстановления ключа. Их первая реализация ломала SIKEp434, набор категории 1, примерно за час на одном ядре; более крупные наборы тоже оказались непригодны, но не все за тот же час. Квантовый компьютер не понадобился: новая связь с классической теорией кривых разрушила предположение схемы.

Уроки: (1) молодое предположение может пасть внезапно и классически; (2) независимые математические основания уменьшают системный риск; (3) переходный гибрид может сохранить защиту, если его комбинатор и протокол доказанно безопасны при стойкости хотя бы одной компоненты и исключают downgrade. Простая конкатенация самодельных секретов или правило «принять любую из двух подписей» такой гарантии не дают. Сам инцидент показывает ценность открытого криптоанализа до массового развёртывания.

Итоги главы

• PQC — классические алгоритмы на задачах без фурье-уязвимой структуры; конкурс NIST отобрал решётки (основной путь), хеши и коды (резерв).
• LWE — линейные отношения с шумом; редукции от худшего случая к среднему дают сильное основание, но не абсолютное доказательство конкретной схемы. Module-LWE делает ML-KEM и ML-DSA практичными.
• Хеш-подписи идут от одноразового Лампорта через деревья Меркла к бесстатусному SLH-DSA; его стандартизованные подписи занимают примерно 7,9–49,9 КБ.
• McEliece и выбранный для будущего стандарта HQC дают независимое кодовое основание; HQC ещё не FIPS.
• Крах SIKE напоминает о криптоаналитической неопределённости; разнообразие и корректно спроектированные гибриды уменьшают, но не автоматически устраняют риск.

Упражнения

1. Игрушечный LWE: q = 17, s = (3, 5). Выберите четыре разных a_i и ошибки e_i ∈ {−1, 0, +1}, вычислите b_i = ⟨a_i, s⟩ + e_i. (а) Переберите все 17² кандидатов и ранжируйте их по суммарному модульному отклонению. (б) Наивно примите b_i за точные правые части и примените Гаусса к разным парам: почему ответы могут конфликтовать? Проследите, как линейные комбинации преобразуют неизвестные e_i. Почему оба подхода плохо масштабируются?
2. Посчитайте размеры схемы Лампорта для k = 256 и 256-битного хеша: секретный ключ, открытый ключ, подпись. Сравните с 3,3 КБ у ML-DSA-65.
3. Покажите атаку на двухразовое использование Лампорта: пусть одним ключом подписаны сообщения с хешами 0011… и 0101…. Какие строки раскрыты и хеши с какими началами противник теперь может подписать сам? Сколько битовых позиций «свободны»?
4. В дереве Меркла на 2²⁰ одноразовых ключей — какова длина пути аутентификации (в хешах) и итоговый размер подписи (Лампорт из упр. 2 + путь)? Что случится, если после восстановления из вчерашнего бэкапа счётчик листьев отстанет на единицу?
5. Сырой ключ ML-KEM-768 (1184 Б) против X25519 (32 Б) — в 37 раз больше, но в TLS передаются key_share обеих сторон: 1216 Б от клиента и 1120 Б от сервера. Сертификатная цепочка содержит отдельные ключи и подписи, а CertificateVerify — ещё одну подпись. Объясните, почему миграция подписей сильнее влияет на размер цепочки; отдельно отметьте, что корневой сертификат обычно не передаётся сервером, а SCT и OCSP зависят от конфигурации.
6. Какие условия нужны, чтобы гибрид X25519 + ML-KEM был не слабее стойкой компоненты: специфицированный комбинатор, связывание с транскриптом, проверка ошибок и защита от downgrade? Опишите два сценария, в которых одна компонента сохраняет защиту (крах решёток; появление CRQC), и контрпример с самодельным комбинатором, где лозунг «нужно сломать обе» неверен.

Ответы и указания. 2: секретный ключ 2·256·32 = 16 КБ, открытый — 16 КБ, подпись 256·32 = 8 КБ. 3: раскрыты обе строки в каждой различающейся позиции; там бит дайджеста свободен, а в совпадающихся позициях должен остаться прежним. Чтобы подписать реальное новое сообщение, ещё надо найти сообщение с подходящим дайджестом. 4: путь — 20 хешей (640 Б); учебная подпись ≈ 8,6 КБ без служебных полей; отставший счётчик повторно использует лист. 5: сервер обычно отправляет лист и промежуточные сертификаты, но не доверенный корень; каждый отправленный сертификат уже несёт подпись издателя, а TLS добавляет CertificateVerify. SCT и stapled OCSP могут добавить другие подписанные объекты, поэтому множитель зависит от цепочки и конфигурации.

Литература к главе

1. O. Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," STOC 2005. arxiv.org/abs/2401.03703 (переиздание)
2. NIST FIPS 203, 204, 205 — стандарты ML-KEM, ML-DSA, SLH-DSA, 2024: FIPS 203, FIPS 204, FIPS 205.
3. NIST, "HQC Announced as a 4th Round Selection," 2025. csrc.nist.gov/News/2025/hqc-announced-as-a-4th-round-selection
4. D. Bernstein, T. Lange, "Post-quantum cryptography," Nature 549, 2017.
5. W. Castryck, T. Decru, "An efficient key recovery attack on SIDH," EUROCRYPT 2023. eprint.iacr.org/2022/975
6. L. Lamport, "Constructing Digital Signatures from a One Way Function," SRI Technical Report, 1979.

Предыдущая глава || Содержание курса || Следующая глава