Pqc

Привет, Хабр. Недавно NIST на своем сайте объявили о старте третьего этапа стандартизации постквантовой криптографии. В третий этап прошли 3 кандидата на цифровую подпись и 4 кандидата на асимметричное шифрование. Так же были представлены 8 альтернативных кандидатов. Я подумал, что хабровчан заинтересует данное событие. Более подробнее под катом.

Немного истории

Идея квантовых вычислений впервые была предложена в начале 1980х годов для моделирования сложных квантово-механических систем. Вскоре оказалось, что квантовые вычисления могут дать огромное ускорение для решения других задач, таких как факторизация чисел и дискретное логарифмирование в группе точек эллиптической кривой.

Это стало существенной проблемой для криптографии, так как безопасность распространенных стандартизированных систем зависит от сложности решения этих задач.
Тем не менее, квантовые вычисления довольно длительное время оставались лишь красивой абстракцией, которую не было технической возможности реализовать. Но в последнее время возможность создания квантовых компьютеров была пересмотрена и это стимулировало NIST запустить в 2016 году открытый конкурс на создание новых постквантовых стандартов. Точнее говоря, NIST заинтересовано в создании новых стандартов асимметричного шифрования (Public-Key Encryption) и цифровой подписи (Digital Signatures).

На участие в конкурсе подали заявки 69 команд со всего мира. Эта тема была широко освещена и даже были посты на хабре. Из предложенных схем во второй этап прошли всего 26. И вот, 22 июля 2020 года, были объявлены финалисты второго этапа, которые прошли дальше. Осталось всего 4 кандидата на асимметричное шифрование и 3 кандидата на цифровую подпись.

Кандидаты прошедшие в третий этап

Итак, кандидаты на новый постквантовый стандарт цифровой подписи:

• CRYSTALS-DILITHIUM Является представителем криптографии на решетках. За основу взята схема Фиата-Шамира с прерываниями. Криптоанализ сводится к решению задач Module-LWE и Module-SIS. Имеет хорошую производительность и может быть эффективно реализована на малоресурсных устройствах. NIST попросили авторов добавить набор общесистемных параметров для 5 уровня безопасности.
• FALCON Так же является представителем криптографии на решетках. Но за основу взят фреймворк GPV. Криптоанализ сводится к задаче SIS на NTRU-решетках. Главным недостатком этой схемы является сложная програмная и апаратная реализация. Схема используют вычисления над числами с плавающей запятой, что сильно усложняет как анализ стойкости к атакам по сторонним каналам, так и делает сложным реализацию для малоресурсных устройств.
• Rainbow Является предствителем криптографии на мультивариативных преобразованиях. За основу взята схема UOV. Главным преимуществом является размер цифровой подписи. Но из-за большого размера ключа эту схему рекомендуется ипользовать только для специфических задач, где размер ключей не критичен.

NIST так же заявили что хотя бы одна из схем CRYSTALS-DILITHIUM и FALCON будет стандартизирована. Таким образом, для цифровой подписи скорей всего в будущем будут использоваться схемы на основе криптографии на решетках. А для более специфических задач Rainbow.

Для асимметричного шифрования в третий этап вышли:

• Classic McEliece Является представителем криптографии на кодах исправляющих ошибки. Основная конструкция схемы была предложена еще в 1979 году и хорошо изучена. Имеет малые размеры шифротекстов, но очень большой размер ключа. Из-за чего имеет те же проблемы, что и Rainbow и рекомендуется к использованию только для специфических задач.
• CRYSTALS-KYBER Является представителем криптографии на решетках. Криптоанализ сводится к решению задачи Module-LWE. Для обеспечения стойкости к атакам с адаптивно подобраными шифротекстами используется преобразование Фуджисаки-Окамото. Имеет хорошую производительность и безопасность, но NIST так же напоминают, что Module-LWE это относительно малоизученная проблема и требует более детального криптоанализа.
  
• NTRU Является представителем криптографии на решетках. За основу взята схема NTRUEncryt, предложенная более 20 лет назад. Проблема NTRU, в отличие от Module-LWE (и других модификаций) была очень хорошо изучена, что является очень важным фактором.
  
• SABER Является представителем криптографии на решетках. Криптоанализ сводится к проблеме MLWR (Module-LWE, где вместо сложения с вектором ошибки используется
  округление по меньшему модулю). Используется преобразование Фуджисаки-Окамото, как и в CRYSTALS-KYBER.
  

В целом, ситуация аналогичная для общего использования рекомендуются схемы на основе решоток. Но NIST сделали замечание, что только одна из схем на решетках (CRYSTALS-KYBER, NTRU, SABER) будет стандартизирована.

Альтернативные схемы

Так же NIST отобрали 8 альтернативных схем, которые не вошли в финал, но являются перспективными.

Среди схем цифровой подписи:

• SPHINCS+ и Picnic являются схемами на основе симметричных криптопримитивов. Криптоанализ SPHINCS+ сводится к стойкости хеш-функций, а Picnic к NIZK и блочным шифрам. Эти схемы являются довольно новыми и малоизучеными. Но основной их недостаток все же в огромном размере подписи, что делает их неприменимым для многих задач.
  
• GeMSS Похожа на Rainbow, но основана на HFE, вместо UOV. Имеет больший размер ключа и более медленный процес подписи. Выбран в качестве альтернативы на случай нахождения уязвимостей в Rainbow.

Среди асимметричного шифрования:

• BIKE Является схемой на кодах исправляющих ошибки. Требует более детального иследования безопасности.
• FrodoKEM Является представителем криптографии на решетках. Криптоанализ сводится к проблеме LWE, которая более изучена чем Module-LWE (и другие разновидности). Имеет слишком медленные алгоритмы шифрования\расшифрования.
  
• HQC Является схемой на кодах исправляющих ошибки. Базируется на квазициклических кодах. Имеет слишком медленные алгоритмы шифрования\расшифрования.
  
• NTRU Prime Является представителем криптографии на решетках. Имеет хорошую защищенность от алгебраических атак.
  
• SIKE Является единственной схемой (среди поданных на конкурс), что базируется на изогениях эллиптических кривых. Требует более детального изучения.
  

Краткие выводы

NIST на протяжении последних четырех лет провели анализ предложенных постквантовых схем со всего мира. Среди предложенных схем доминирующую позицию занимают схемы на решетках. Но они (как и другие направления) требуют более детального изучения. NIST планирует в течении ближайших 3 лет провести детальный анализ оставшихся кандидатов.

Стоит заметить, что в мире уже есть стандартизированные схемы на решетках: раз ,два. Так что, скорей всего, именно криптография на решетках в ближайшие годы все больше будет вытеснять привычные RSA и ECDSA. Но в то же время в узкоспециализированных областях будут популярны иные решения.