NIST объявило о начале третьего этапа стандартизации постквантовой криптографии

Привет, Хабр. Недавно 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. Но в то же время в узкоспециализированных областях будут популярны иные решения.

Похожие публикации

Средняя зарплата в IT

113 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 5 065 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 9

    0
    Стоит добавить, что BIKE и SIKE поддерживается со стороны AWS:

    aws.amazon.com/blogs/security/post-quantum-tls-now-supported-in-aws-kms
      0
      Ради интереса.
      Если здесь есть специалисты или энтузиасты постквантовой криптографии, могли бы пояснить один момент?
      Когда писал диплом и разбирался в текущих «трех» направлениях — решётки, коды и многомерка, с удивлением обнаружил, что математически первые два сводятся к одной и той же задаче. Еднственное отличие, что решётки почему-то принято демонстрировать в графическом виде, а коды по традиции идут в алгебраическом.
      Кто-то может пояснить, есть ли там действительно разные задачи, или просто «исторически сложилось» два направления и их так и развивают?
        +1
        Первые сводятся как правило к задаче нахождения наименьшего вектора на решетке. Вторые сводятся к задаче декодирования линейного кода. Обе эти задачи являются NP-полными и могут быть сведены друг к другу. Так что нет ничего удивительного, что математика выглядит похожей. Но state-of-the-art методы криптоанализа систем имеют разную сложность и используют отличные друг от друга методы, поэтому имеет смысл разнести задачи по отдельным классам.
        +2
        NIST на протяжении последних четырех лет провели анализ предложенных постквантовых схем со всего мира

        Не только NIST, но и многие команды математиков по всему миру проводили анализ. Мне даже посчастливилось работать в одной из.
          0
          Да, я немного неправильно выразился в статье. Спасибо за замечание! А каким направлением вы занимаетесь, если не секрет?
            0
            Мы занимались анализом WalnutDSA, который был одной из 69 схем, предложенных на первом этапе.
          +3
          Стоит отметить, что у алгоритмов на решетках есть небольшая, но всё же вероятность получения ошибки при дешифровке (декапсуляции). Для CRYSTALS-KYBER и Saber они составляют 1 на 2^120 — 1 на 2^160.
          Это не представляет проблем для online коммуникаций, там можно всё переслать. Но для оффлайн хранения данных c долгоживущими ключами есть небольшая вероятность, что файл, который будет зашифрован ключом, полученным из протокола на решетках, невозможно будет расшифровать.

          Как вариант, симметричный ключ для таких случаев можно энкапсулировать дважды, но этим никто заморачиваться, конечно, не будет.
          Такие дела
            0
            Стоит отметить, что у алгоритмов на решетках есть небольшая, но всё же вероятность получения ошибки при дешифровке (декапсуляции). Для CRYSTALS-KYBER и Saber они составляют 1 на 2^120 — 1 на 2^160.
            Согласен, есть такая неприятная особенность у некоторых PKE/KEM на решетках, но не во всех же! У NTRU нет ошибок декапсуляции (Хотя в оригинальном NTRUEncrypt они были). У NTRU Prime (из алтернативных кандидатов) так же нет ошибок декапсуляции. По поводу величины ошибки -имхо, — 1 на 2^120 — 1 на 2^160 достаточно низкая вероятность, чтобы о ней можно было даже не беспокоиться (может, за исключением каких-то критических систем).
              0

              Это ничтожная вероятность ошибки для большинства практических применений. Гораздо меньше вероятности сгенерировать 2 одинаковых GUID'а подряд.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое