Конкурс NIST PQC: процесс и критерии

NIST запустил проект стандартизации постквантовой криптографии (PQC) в 2016 году в прямой ответ на угрозу, которую создают квантовые компьютеры. Алгоритм Шора может взломать RSA и криптографию на эллиптических кривых за полиномиальное время на достаточно большом квантовом компьютере. NIST осознал, что переход криптографической инфраструктуры занимает десятилетия, и начал этот процесс задолго до того, как квантовые компьютеры стали непосредственной угрозой.

В декабре 2016 года NIST объявил о приёме заявок и к ноябрю 2017 года получил 82 полные заявки. После первичного рассмотрения 69 из них были приняты в качестве кандидатов первого раунда. Заявки охватывали широкий спектр математических предположений: задачи на решётках, хеш-функции, кодовую криптографию, изогенную криптографию и многомерные многочлены. Разнообразие предположений было одной из главных целей, чтобы не складывать все яйца в одну корзину.

В первом раунде NIST и всё криптографическое сообщество провели интенсивный анализ всех 69 кандидатов. Критерии включали стойкость (противодействие классическим и квантовым атакам), производительность (размеры ключей и шифротекстов, скорость вычислений), гибкость (наборы параметров для разных уровней стойкости) и простоту реализации. К январю 2019 года 26 кандидатов вышли во второй раунд.

26 кандидатов второго раунда прошли более глубокий криптоанализ и сравнительное тестирование производительности. В ходе этого раунда несколько схем были взломаны или ослаблены, включая Rainbow (многомерная криптография) и SIKE (изогенная криптография, хотя SIKE была взломана только в третьем раунде). К июлю 2020 года 15 кандидатов вышли в третий раунд, разделившись на 7 финалистов и 8 запасных кандидатов.

Семью финалистами третьего раунда стали Kyber, NTRU и SABER (KEM), а также Dilithium, FALCON, Rainbow и SPHINCS+ (схемы подписи). SIKE была запасным кандидатом, но в 2022 году её взломали с поразительной лёгкостью. NIST выбрал Kyber для стандартизации KEM благодаря продуманной архитектуре, убедительным доказательствам стойкости и отличной производительности. Для схем подписи были выбраны Dilithium, FALCON и SPHINCS+.

NIST намеренно выбирал алгоритмы, основанные на разных математических задачах, чтобы снизить риски, связанные с будущими открытиями. ML-KEM и ML-DSA опираются на модульный LWE (решётки). FALCON опирается на решётки NTRU и гауссовскую выборку. SLH-DSA полагается только на стойкость хеш-функций. Если будет найден способ атаковать решётки, SLH-DSA сохранит стойкость, обеспечивая алгоритмическое разнообразие стандартизованного набора.

В 2022 году NIST открыл четвёртый раунд, специально запросив дополнительные кандидатуры схем подписи. Это было обусловлено желанием расширить разнообразие схем подписи за пределами решёточных схем. Среди кандидатов были MAYO, CROSS, UOV и другие схемы, основанные на многомерных и кодовых предположениях. Этот процесс шёл параллельно с завершением подготовки первых трёх стандартов (FIPS 203, 204 и 205).

NIST опубликовал окончательные стандарты PQC в августе 2024 года: FIPS 203 (ML-KEM на основе Kyber), FIPS 204 (ML-DSA на основе Dilithium) и FIPS 205 (SLH-DSA на основе SPHINCS+). Ожидается, что вслед за ними выйдет FIPS 206 (FN-DSA на основе FALCON). Теперь эти стандарты необходимо учитывать федеральным ведомствам US, и они влияют на стандарты во всём мире через ISO, ETSI и IETF.

IETF быстро внедрял PQC в протоколы. К 2024 году разрабатывались проекты RFC по ML-KEM в TLS 1.3, SSH и сертификатах X.509. Cloudflare, Google и Amazon объявили о планах внедрить ML-KEM в свои стеки TLS. Apple объявила о PQ3 для iMessage, использующем ML-KEM для постквантовой прямой секретности на основе цепочки смены ключей; эта технология была развёрнута более чем на миллиарде устройств.

Конкурс NIST PQC продемонстрировал, что открытая совместная стандартизация криптографических решений работает эффективно. В ходе процесса были взломаны несколько высоко оценённых схем (GeMSS, SIKE и Rainbow), что подтвердило важность широкого публичного криптоанализа. Конкурс также стимулировал разработку эффективных аппаратных реализаций и библиотек с открытым исходным кодом (liboqs, PQClean), ускоривших внедрение.

Стандартизация постквантовой криптографии ещё не завершена. NIST продолжает оценивать дополнительные схемы подписи для обеспечения разнообразия. Орган по финансовым стандартам X9 разрабатывает стандарты PQC для банковской отрасли. ETSI и ISO приводят свои стандарты в соответствие с NIST FIPS. Разрабатываются рекомендации по переходу для отдельных отраслей: здравоохранения (последствия требований HIPAA), оборонной отрасли (набор CNSA 2.0 от NSA) и телекоммуникаций (3GPP для 5G/6G).

Сколько кандидатов вышло из числа первоначальных заявок во второй раунд конкурса NIST PQC?

В 2016 году NIST запустил проект стандартизации PQC, получив 69 полных заявок. Три раунда оценки сократили число кандидатов на основе таких критериев, как безопасность, производительность и разнообразие. В итоге были выбраны Kyber (ML-KEM, FIPS 203), Dilithium (ML-DSA, FIPS 204), SPHINCS+ (SLH-DSA, FIPS 205) и FALCON (FN-DSA, FIPS 206). Конкурс подтвердил важность открытого криптоанализа и привёл к появлению широко принятых стандартов, которые теперь внедряются в протоколы TLS, SSH и обмена сообщениями.