Подробно Основные направления синтеза квантово-устойчивых алгоритмов включают:
- Использование теории целочисленных решеток (lattice-based cryptography): задача поиска кратчайшего вектора решетки и ее варианты, задача обучения с ошибкой;
- Использование кодов, исправляющих ошибки (code-based cryptography): задача декодирования случайного кода;
- Использование многочленов от многих переменных (multivariate cryptography): задача решения нелинейной системы уравнений;
- Использование криптографических хэш-функций (hash-based cryptography): задачи поиска коллизии/прообраза/второго прообраза для криптографических хэш-функций;
- Использование изогений суперсингулярных эллиптических кривых (supersingular isogeny-based cryprography): задача поиска пути в графе изогений.
«Экзотика»: - проблемы сопряженного поиска (search problem);
- операции в группах кос (braid groups);
- алгебра октонионов;
- многочлены Чебышёва;
- и так далее.
На примере алгоритмов-финалистов
конкурса NIST и
разработок команды QApp —
библиотеки квантово-устойчивых алгоритмов PQLR SDK — можно видеть как современные синтезные концепции находят реализацию в конкретных криптографических схемах.
Так, задачи теории решеток лежат в основе алгоритмов-финалистов конкурса NIST: CRYSTALS-KYBER, NTRU, SABER (реализован в нашем продукте PQLR SDK), CRYSTALS-DILITHIUM и FALCON, альтернативных алгоритмов-финалистов FrodoKEM и NTRU Prime.
Задачи теории кодирования обеспечивают стойкость таких алгоритмов-финалистов конкурса NIST, как Classic McEliece (реализован в нашем продукте PQLR SDK) и альтернативных алгоритмов-финалистов BIKE, HQC.
На основе многочленов от многих переменных строятся финалист конкурса NIST Rainbow и альтернативный алгоритм-финалист GeMSS.
Большое внимание уделяется криптографическим алгоритмам на основе хэш-функций. Так, алгоритм-финалист конкурса NIST XMSS и альтернативный алгоритм-финалист SPHINCS+ реализованы в PQLR SDK. Команда QApp активно сотрудничает с разработчиками алгоритма XMSS в части обоснования криптостойкости алгоритма, а также принимает участие в деятельности рабочей группы РГ 2.5 «Постквантовые криптографические механизмы» ТК 26 «Криптографическая защита информации» с целью стандартизации в России схемы цифровой подписи, основанной на хэш-функциях.
Алгоритмы на основе изогений суперсингулярных эллиптических кривых представлены в финале конкурса NIST схемой SIKE. Специалисты команды QApp активно участвуют в работе РГ 2.5 «Постквантовые криптографические механизмы» ТК 26 в части стандартизации отечественного алгоритма «Форзиция», основанного на сложных задачах из этого класса.
Наконец, единственный альтернативный финалист конкурса NIST из класса «экзотических» — схема цифровой подписи Picnic — основана на доказательствах с нулевым разглашением. Можно отметить, что на алгоритмы из этого класса пришлось наибольшее количество успешных атак среди всех 69 участников конкурса NIST.