Post-Quantum криптография

В 2022 году SIKE - один из кандидатов на post-quantum стандарт с самыми компактными ключами - был взломан классическим алгоритмом за 1 час на ноутбуке. PQC требует осторожности.

• NIST FIPS 203/204/205 (август 2024): первые официальные post-quantum стандарты - начало эры PQC
• Google Chrome 2023: гибридный X25519+Kyber для TLS - миллиарды соединений уже используют PQC
• Apple iMessage PQ3 (2024): Kyber для обновления ключей каждый день - strongest PQC deployment в consumer apps
• Signal 2024: PQXDH протокол с Kyber для X3DH - мессенджер с 40M+ пользователей

Kyber - решёточное шифрование

CRYSTALS-Kyber (теперь ML-KEM, FIPS 203) - победитель конкурса NIST 2022 для Key Encapsulation Mechanism. Основан на задаче Module Learning With Errors (M-LWE): дано множество пар (A, b = As + e) где s - секрет, e - малый шум, восстановить s. Эта задача предположительно сложна и для классических, и для квантовых компьютеров. Kyber-768 обеспечивает ~AES-192 стойкость, Kyber-1024 - ~AES-256.

Производительность Kyber сравнима с RSA на уровне реализации: Kyber-768 keygen - 0.04 мс, encaps - 0.05 мс, decaps - 0.06 мс на современном CPU. RSA-2048 keygen - ~1 мс. Размеры: Kyber-768 публичный ключ - 1184 байта (RSA-2048 - 256 байт), ciphertext - 1088 байт. Google Chrome включил Kyber в 2023 для TLS. Signal Protocol планирует добавить Kyber для X3DH.

Dilithium - решёточные подписи

CRYSTALS-Dilithium (ML-DSA, FIPS 204) - цифровая подпись на основе Module Learning With Errors. Схема Fiat-Shamir с решёточным commitment: prover показывает что знает s без его раскрытия. Безопасность основана на M-LWE и M-SIS (Module Short Integer Solution). Dilithium3 (~AES-192): подпись 3293 байта, публичный ключ 1952 байта. Для сравнения: ECDSA P-256 подпись 64 байта, ключ 32 байта.

FALCON (FIPS 206) - альтернативная lattice подпись с меньшим размером (подпись ~666 байт для уровня AES-128), основан на NTRU решётках. Mais сложен в реализации без побочных каналов. Dilithium более консервативный выбор для большинства применений. Производительность Dilithium3: keygen - 0.08 мс, sign - 0.1 мс, verify - 0.08 мс. Быстрее RSA-2048 в 10x по ключегенерации.

SPHINCS+ - подписи на хэш-функциях

SPHINCS+ (SLH-DSA, FIPS 205) - единственный финалист NIST не основанный на решётках. Безопасность целиком зависит от стойкости хэш-функций (SHA-256 или SHAKE). Дерево Меркла + one-time signatures (WOTS+) + few-time signatures (FORS) образуют иерархическую схему. Преимущество: минимальные предположения безопасности. Недостаток: большие подписи (8-50 кБ).

Hash-based signatures исторически первые post-quantum подписи: Lamport OTS (1979), Merkle Signature Scheme (1989). SPHINCS+ - современная многоразовая схема без stateful ограничений (в отличие от XMSS). Применение: long-term подписи, Certificate Transparency, firmware signing где скорость подписания не критична. Основное применение Dilithium - interactive protocols, SPHINCS+ - batch offline signing.

Code-based и другие PQC подходы

Code-based криптография основана на сложности декодирования случайных линейных кодов (синдромная задача декодирования - NP-полная). McEliece 1978 - старейшая post-quantum схема, не взломанная за 45 лет. Classic McEliece включён в NIST Round 4 как альтернатива. Недостаток: огромные ключи (Classic McEliece-8192128: публичный ключ - 1 МБ). Подходит для специализированных применений с большой пропускной способностью.

Isogeny-based криптография (SIDH/SIKE) - ещё один подход, самые компактные ключи среди PQC. SIKE был взломан в 2022 классической атакой (не квантовой!) командой Wouter Castryck и Thomas Decru - 1 час на ноутбуке. Напоминание: PQC схемы также могут быть взломаны классическим криптоанализом. Поэтому NIST проводил 8-летний конкурс с интенсивным криптоанализом. Lattice-схемы прошли наиболее тщательную проверку.

Новая эра криптографии

• ML-KEM (Kyber): решёточный KEM на LWE, FIPS 203, производительность сравнима с RSA при большем размере ключей
• ML-DSA (Dilithium): решёточные подписи, FIPS 204, в 10x быстрее RSA по keygen, подпись 3.3 кБ
• SLH-DSA (SPHINCS+): hash-based подписи, FIPS 205, минимальные предположения безопасности, подпись 8-50 кБ
• SIKE взломан 2022: напоминание - PQC схемы требуют тщательного криптоанализа, выбирать NIST-финалисты

Связанные темы

Post-quantum криптография - прямой ответ на квантовую угрозу и замена классическим асимметричным схемам

• Квантовая угроза — Алгоритм Шора - мотивация для разработки ML-KEM/ML-DSA
• Секретное совместное использование — ZKP и threshold схемы адаптируются для post-quantum мира
• ZK-SNARK'и — Lattice-based ZK доказательства - активная область research в PQC

Вопросы для размышления

• Если Kyber имеет ключи в 5x больше RSA-2048 при похожей производительности, какие практические системы пострадают больше всего от перехода на PQC? Что придётся пересматривать в протоколах?

Связанные уроки

• la-01-vectors-intro