NIST выбрал алгоритмы шифрования, устойчивые к квантовым вычислениям

Национальный институт стандартов и технологий США (NIST) объявил победителей конкурса криптоалгоритмов, стойких к подбору на квантовом компьютере. Он стартовал шесть лет назад и был нацелен на выбор алгоритмов постквантовой криптографии, пригодной для выдвижения в качестве стандартов. Выбранные алгоритмы шифрования станут частью постквантового криптографического стандарта NIST, который, как ожидается, будет завершён примерно через два года.

Победителем среди универсальных алгоритмов, которые можно использовать для защиты передачи информации в компьютерных сетях, выбрали CRYSTALS-Kyber, сильные стороны которого — относительно небольшой размер ключей и высокая скорость работы. Кроме CRYSTALS-Kyber выделили ещё четыре алгоритма общего назначения — BIKE, Classic McEliece, HQC и SIKE, которые требуют доработки. Авторам этих алгоритмов предоставили возможность до 1 октября устранить недочёты, после чего их могут включить в число финалистов.

Оставленные для доработки универсальные алгоритмы основаны на иных принципах: в BIKE и HQC использовали элементы теории алгебраического кодирования и линейные коды, также применяемые в схемах коррекции ошибок. NIST намерен дополнительно стандартизировать один из этих алгоритмов для альтернативы CRYSTALS-Kyber, основанному на теории решёток. Алгоритм SIKE базируется на использовании суперсингулярной изогении (кружение в суперсингулярном изогенном графе) и также рассматривается в качестве кандидата на стандартизацию, так как отличается наименьшим размером ключа.

Из алгоритмов, нацеленных на работу с цифровыми подписями, выделили CRYSTALS-Dilithium, FALCON и SPHINCS+. Алгоритмы CRYSTALS-Dilithium и FALCON отличаются высокой эффективностью. В качестве первичного алгоритма для цифровых подписей рекомендовали CRYSTALS-Dilithium, FALCON ориентирован на решения, в которых требуется минимальный размер подписи. SPHINCS+ отстаёт от первых двух алгоритмов по размеру подписей и скорости работы, но его оставили в числе финалистов в качестве запасного варианта. 

В алгоритмах CRYSTALS-Kyber, CRYSTALS-Dilithium и FALCON использовали методы криптографии, основанные на решении задач теории решёток, время решения которых не отличается на обычных и квантовых компьютерах. Алгоритм SPHINCS+ применяет методы криптографии на основе хеш-функций.