Конкурс NIST по выбору квантово-устойчивых криптоалгоритмов
На английском языке: NIST Post-quantum competition
Коротко

Конкурс NIST по выбору квантово-устойчивых криптоалгоритмов (далее «Конкурс NIST») — это комплекс мероприятий, организованный Национальным институтом стандартов и технологий США (National Institute of Standards and Technology, NIST) с целью стандартизации набора квантово-устойчивых криптографических схем инкапсуляции ключа и цифровой подписи. Конкурс стартовал в 2017 году, в настоящий момент завершен его третий раунд. Экспертами NIST из 69 алгоритмов-кандидатов, представленных группами разработчиков из разных стран, в том числе международными, выделено 4 алгоритма, которые будут стандартизированы, а также объявлено о проведении дополнительного четвертого раунда для расширения набора стандартизированных алгоритмов. По опыту ранее проводимых NIST аналогичных конкурсов по выбору блочного шифра (AES) и функции хэширования (SHA-3), процесс стандартизации квантово-устойчивых алгоритмов может завершиться в 2024 году.
    Подробно

    После публикации в 1994-1995 годах алгоритма Шора для факторизации и дискретного логарифмирования, квантовая угроза стала серьезным предметом для беспокойства среди разработчиков и пользователей средств криптографической защиты информации, ведь в случае появления квантового компьютера достаточной производительности наиболее популярные асимметричные схемы шифрования и цифровой подписи, в том числе RSA, DSA, ГОСТ Р 34.10-2012, становятся уязвимыми.

    Начиная с 2017 года процессы исследования в области синтеза и анализа квантово-устойчивых криптографических схем получили новый импульс благодаря усилиям Национального института стандартов и технологий США (National Institute of Standards and Technology, NIST), организовавшего открытую международную площадку (конкурс) для подачи предложений по стандартизации и обсуждения постквантовых криптографических схем.

    Алгоритмы-кандидаты, поданные для участия в конкурсе NIST, реализуют следующие механизмы: инкапсуляцию ключей и цифровую подпись. К этим механизмам предъявляются определенные требования по стойкости, как теоретической (формально доказуемой), так и практической (определены несколько уровней стойкости относительно всех известных квантовых и классических атак). Важным критерием является также практическая применимость предлагаемых алгоритмов.

    Алгоритмы проходят как внутреннюю экспертизу силами сотрудников NIST, так и открытую валидацию стараниями криптографов-исследователей со всего мира. Результаты экспертизы обсуждаются как непосредственно на сайте NIST, так и в публичном списке рассылки.

    Ход конкурса NIST

    Прием заявок на участие в конкурсе NIST завершен 30 ноября 2017 г. Всего к участию в конкурсе было допущено 69 заявок, 14 из них были отозваны авторами или взломаны уже на первом раунде.

    Основные направления синтеза криптографических схем, применяемые в алгоритмах-участниках конкурса NIST:
    • сложные задачи теории целочисленных решеток (lattice-based cryptography);
    • использование кодов, исправляющих ошибки (error-correcting codes);
    • схемы цифровой подписи на основе криптографических хэш-функций (hash-based cryptography);
    • системы многочленов от многих переменных (multivariate cryptography);
    • сложные задачи, связанные с изогениями суперсингулярных эллиптических кривых (supersingular isogeny-based cryptography);
    • «экзотические» задачи, такие как проблемы сопряженного поиска (Search Problem), операции в группах кос (Braid Groups), алгебра октонионов, многочлены Чебышёва и т.д.

    30 января 2019 г. NIST опубликовал перечень из 26 алгоритмов-кандидатов, прошедших на второй раунд конкурса. При этом эксперты NIST не высказали явного предпочтения в выборе классов перспективных синтезных решений. Исключены из числа участников были лишь экзотические схемы, зачастую оказывающиеся наименее стойкими.

    Следующим этапом являлось внесение правок и улучшений в прошедшие на второй раунд схемы, для этого был отведен срок до 15 марта 2019 г.

    В июле 2020 г. NIST анонсировал третий раунд процесса стандартизации, который продлился 24 месяца. В него прошли 15 алгоритмов (7 основных и 8 альтернативных).
    В июле 2022 завершился третий раунд конкурса NIST, был объявлен финальный список алгоритмов для стандартизации в США.
    В число отобранных алгоритмов вошли:

    • схемы цифровой подписи CRYSTALS-Dilithium, Falcon, SPHINCS+;
    • схема защищенной передачи ключа CRYSTALS-Kyber.

    Дополнительно был объявлен четвертый раунд по расширению набора алгоритмов защищенной передачи ключа. В качестве кандидатов рассматриваются алгоритмы Classic McEliece, BIKE, HQC.

    В июле 2023 года NIST опубликовал перечень схем цифровой подписи, допущенных до участия в конкурсе на дополнительный квантово-устойчивый стандарт

    В перечень вошло 40 схем (из 50 поданных), основанных на различных синтезных принципах, в их числе задачи теории решеток, кодирования, хэш-функций и другие. Интерес представляет возвращение схем, основанных на пересмотренных задачах изогений эллиптических кривых и системах нелинейных уравнений, учитывая, что в результате первого конкурса NIST схемы этих классов (SIKE, Rainbow) были скомпрометированы.

    Напомним, что основной причиной проведения дополнительного раунда стал тот факт, что наиболее эффективные схемы-победители основного этапа (CRYSTALS-Dilithium, Falcon) основаны на задачах теории решеток, а третий финалист – SPHINCS – уступает им по производительности.

    По состоянию на август 2023 года, для ряда схем из нового перечня (FuLeeca, KAZ-Sign, LESS, MEDS, Alteq) уже продемонстрированы достаточно эффективные атаки.

    Наконец, в августе 2023 года NIST опубликовал проекты стандартов:
    SPHiNCS+
    Dilithium
    Kyber
    Конкурс NIST самим фактом своего проведения оказал значительное влияние на развитие методов синтеза и анализа новых квантово-устойчивых криптографических схем. Эксперты NIST и представители международного криптографического сообщества за прошедшие 3 раунда проанализировали более 80 алгоритмов-кандидатов.
    Компания QApp активно вовлечена в процесс международной стандартизации квантово-устойчивых алгоритмов

    Команда QApp активно следит за конкурсом квантово-устойчивых алгоритмов NIST. Каждый алгоритм проходит валидацию и анализ командой QApp, что позволяет:
    • проактивно добавлять наиболее перспективные алгоритмы из списка NIST в уже существующие продукты компании QApp;
    • сообщать представителям NIST и международному криптографическому сообществу о найденных ошибках и возможных улучшениях в конкурсных алгоритмах.
    Так, команда QApp сообщила в NIST об обнаружении ошибки в доказательстве безопасности алгоритма подписи SPHINCS+ и вместе с авторами алгоритма провела работу по устранению ошибки.