Постквантовая криптография: стандарты США
Коротко

13 августа 2024 года Национальный институт стандартов США (NIST) опубликовал окончательные версии первых стандартов в области постквантовой криптографии:
Подробно

Алгоритмы к стандартизации были выбраны по итогам конкурса, анонсированного NIST еще в 2016 году. В число отобранных алгоритмов, помимо включённых в недавно опубликованные стандарты, также вошла схема цифровой подписи Falcon, получившая новое обозначение FN-DSA. Соответствующий стандарт (FIPS 206) находится в разработке.

Стандарт FIPS 203 (ML-KEM) является механизмом инкапсуляции ключа, используемом для безопасной выработки сессионного ключа. В свою очередь, сессионный ключ необходим для обслуживания защищенного соединения. Стойкость алгоритма инкапсуляции ключа ML-KEM, ранее известного как KYBER, основывается на сложности решения задачи M-LWE из теории алгебраических решёток. Существует множество теоретических исследований задачи M-LWE, укрепляющих предположение об экспоненциальной сложности ее решения как на классическом, так и на квантовом компьютере.

Стандарт постквантовой цифровой подписи FIPS 204 (ML-DSA), ранее известный как Dilithium, также основан на сложности решения задач из теории решеток. В случае с ML-DSA такими задачами являются уже упомянутая M-LWE и задача M-SIS, которая также хорошо исследована, как и задача M-LWE. Цифровая подпись служит для аутентификации и подтверждения авторства отправителя сообщения. В связи с этим, алгоритмы цифровой подписи, наравне с механизмами инкапсуляции ключа, являются необходимыми инструментами для создания защищенного соединения (в том числе в сети Интернет).

Алгоритм цифровой подписи SLH-DSA, ранее известный как SPHINCS+, выполняет те же функции, что и ML-DSA, но его безопасность основана на задачах из другой области. Именно, стойкость данной схемы основывается на сложности нахождения прообраза криптографической хэш-функции. В настоящее время не существует эффективных алгоритмов решения этой задачи, в том числе и квантовых. Стандарт FIPS 205 является запасным вариантом на случай, если в будущем будет найдена уязвимость в ML-DSA, так как алгоритм SLH-DSA является менее производительным по сравнению с ML-DSA.

Итого два стандарта из трех относятся к области криптографии на решетках. Это связано с тем, что на сегодняшний день криптографические алгоритмы, основанные на задачах из теории решёток, достигают наилучшего компромисса между скоростью работы и размерами используемых криптографических ключей. Отметим также, что и алгоритм FN-DSA, стандартизация которого все еще не завершена, также основывается на задачах из теории решеток. Однако нельзя не отметить достоинства алгоритма SLH-DSA, относящегося к классу схем на хэш-функциях. В сравнении со схемами на решетках, он считается безопасным за счет более строгих и консервативных математических предположений. Также он обладает более коротким открытым ключом.

Несмотря на то, что в настоящее время квантовые компьютеры не имеют достаточного числа кубит для успешного взлома классических криптографических алгоритмов, NIST настаивает на скорейшем внедрении уже вышедших стандартов FIPS 203, FIPS 204, FIPS 205.

Все три новых стандарта уже реализованы в кодовой базе основных программных продуктов QApp, и доступны для интеграции в существующие инфраструктурные решения клиентов и партнеров в рамках пилотных проектов и для реализации опытно-конструкторских работ.