Новый конкурс NIST по выбору квантово-устойчивой электронной подписи
На английском языке: NIST Post-quantum competition
Коротко

 По завершении третьего раунда основного конкурса NIST в качестве стандартов выбраны три схемы электронной подписи и одна схема инкапсуляции ключа. После этого был объявлен еще один конкурс по стандартизации схем электронной подписи. Ввиду того, что две из трех выбранных в третьем раунде вариантов электронной подписи построены на структурных решетках, в новом конкурсе упор сделан на выбор схем, построенных на альтернативных криптографических примитивах, не использующих теорию решеток.

Всего на конкурс было заявлено 40 схем электронной подписи, среди которых 7 ― это схемы на решетках. Предложенные варианты пройдут экспертизу и тестирование сотрудниками NIST, а также будут анализироваться международным криптографическим сообществом.
Подробно

В июле 2022 года завершился третий раунд конкурса NIST, в результате которого было предложены к стандартизации три схемы электронной подписи и одна схема инкапсуляции ключа, а в 2023 году вышли первые черновики стандартов FIPS для них. Примечательно, что две из трех выбранных схем электронной подписи построены на структурных решетках. После окончания третьего раунда конкурса, NIST анонсировал дополнительный раунд, в котором рассматриваются четыре схемы инкапсуляции ключа. Также был запущен конкурс на разработку электронной подписи для дальнейшей стандартизации. В связи с тем, что среди предложенных к стандартизации алгоритмов электронной подписи преобладают криптографические схемы, построенные на решетках, в новом конкурсе NIST в первую очередь будут рассматриваться варианты, построенные на других криптографических примитивах. Варианты на структурных решетках также могут быть поданы на рассмотрение, но будут стандартизированы, только если значительно превзойдут ранее выбранные схемы по эффективности.
      17 июля 2023 года был опубликован полный перечень схем электронной подписи первого раунда нового конкурса на стандартизацию. Всего было заявлено 40 алгоритмов, среди которых:

      • 6 схем, построенных на кодах, исправляющих ошибки (code-based signatures);
      • 1 схема, построенная на изогениях эллиптических кривых (isogeny signatures);
      • 7 схем, построенных на теории решеток (lattice-based signatures);
      • 7 схем, построенных на протоколах конфиденциальных вычислений (MPC-in-the-Head signatures);
      • 10 схем, построенных на системах многочленов от многих переменных (multivariate signatures);
      • 4 схемы, построенные на симметричных криптографических алгоритмах, в эту категорию также вошли схемы на основе криптографических хэш-функций (symmetric signatures);
      • 5 схем, не принадлежащих ни одной из категорий, построенных на различных "экзотических" проблемах или структурах (other signatures).

      В отличие от предыдущего этапа, в новом конкурсе появилось целых два новых направления:

      • схемы, построенные на конфиденциальных вычислениях;
      • схемы, построенные на симметричных алгоритмах.

      На текущий момент все анонсированные схемы анализируются международным криптографическим сообществом. На момент этой публикации были найдены уязвимости в ряде предложенных схем:

      • 3 из 6 кодовых схем;
      • 3 из 7 схем на решетках;
      • 1 из 7 схем на протоколах конфиденциальных вычислений;
      • 4 из 10 схем, построенных на многомерных уравнениях;
      • 4 из 5 схем вне категорий.

      Подробнее с комментариями с указанием уязвимостей и атак можно ознакомиться на официальном сайте NIST, подписавшись на рассылку.

      Для ряда схем уязвимости были найдены в их программной реализации, для других были найдены значительные проблемы в обосновании безопасности, а для некоторых из них уже реализованы атаки на восстановление секретного ключа, например, для 3WISE, DME-Sign, EHTv3, EagleSign, HPPC, KAZ-sign, Xifrat1-Sign, eMLE-Sig.

      Сравнив электронные подписи по показателям производительности, можно выделить ряд работ, для которых пока не найдено уязвимостей, с наилучшими показателями компактности размеров "подпись+открытый ключ" и времени работы алгоритмов подписи.

      По компактности лучшими схемами на данный момент являются:
      • SQISign (подпись на изогениях);
      • MAYO (подпись на многомерных уравнениях);
      • Hawk (подпись на решетках).
      По быстродействию алгоритмов выработки подписи лучшие варианты: UOV, MAYO и TUOV (подписи на многомерных уравнениях), а так же подпись на решетках Hawk.