Квантово-устойчивые криптографические алгоритмы
Синонимы: Постквантовые алгоритмы
Коротко
- Квантово-устойчивые (постквантовые) криптографические алгоритмы — это семейство асимметричных криптографических алгоритмов, стойких как относительно классических атак, так и атак с использованием квантового вычислителя (квантовых атак);
- Наиболее распространенные в настоящее время асимметричные криптографические алгоритмы, такие как RSA, DSA, ГОСТ Р 34.10-2018, не являются квантово-устойчивыми, поскольку уже сейчас известны эффективные квантовые алгоритмы (метод Шора для факторизации и дискретного логарифмирования) для их анализа. В то же время, симметричным криптографическим алгоритмам, таким как блочные шифры ГОСТ Р 34.12-2018, AES и хэш-функции ГОСТ Р 34.10-2018, SHA-3, квантовый компьютер угрожает в меньшей степени, поскольку, хотя известные квантовые методы и понижают оценку трудоемкости их анализа, анализ по-прежнему нереализуем в обозримое время;
- Таким образом, для достижения квантовой устойчивости асимметричных криптографических схем, понадобилось обратиться к новым классам вычислительно сложных задач. Известные на данный момент классы таких задач включают в себя задачи теории решеток, теории кодов, исправляющих ошибки, многочленов от многих переменных, криптографических хэш-функций и другие.
Подробно
Основные направления синтеза квантово-устойчивых алгоритмов включают:
«Экзотика»:
На примере алгоритмов-финалистов конкурса NIST можно видеть как современные синтезные концепции находят реализацию в конкретных криптографических схемах.
Так, задачи теории решеток лежат в основе алгоритмов-финалистов конкурса NIST: CRYSTALS-KYBER, CRYSTALS-DILITHIUM и FALCON.
Задачи теории кодирования обеспечивают стойкость таких алгоритмов-участников дополнительного раунда конкурса NIST, как Classic McEliece, BIKE, HQC.
На данный момент сотрудники QApp принимают активное участие в деятельности рабочих подгрупп ТК 26 «Криптографическая защита информации» с целью стандартизации в России схем цифровой подписи и выработки ключа.
Основные направления синтеза квантово-устойчивых алгоритмов включают:
- Использование теории целочисленных решеток (lattice-based cryptography): задача поиска кратчайшего вектора решетки и ее варианты, задача обучения с ошибкой;
- Использование кодов, исправляющих ошибки (code-based cryptography): задача декодирования случайного кода;
- Использование многочленов от многих переменных (multivariate cryptography): задача решения нелинейной системы уравнений;
- Использование криптографических хэш-функций (hash-based cryptography): задачи поиска коллизии/прообраза/второго прообраза для криптографических хэш-функций.
«Экзотика»:
- проблемы сопряженного поиска (search problem);
- операции в группах кос (braid groups);
- алгебра октонионов;
- многочлены Чебышёва;
- и так далее.
На примере алгоритмов-финалистов конкурса NIST можно видеть как современные синтезные концепции находят реализацию в конкретных криптографических схемах.
Так, задачи теории решеток лежат в основе алгоритмов-финалистов конкурса NIST: CRYSTALS-KYBER, CRYSTALS-DILITHIUM и FALCON.
Задачи теории кодирования обеспечивают стойкость таких алгоритмов-участников дополнительного раунда конкурса NIST, как Classic McEliece, BIKE, HQC.
На данный момент сотрудники QApp принимают активное участие в деятельности рабочих подгрупп ТК 26 «Криптографическая защита информации» с целью стандартизации в России схем цифровой подписи и выработки ключа.