Почему ждать новые постквантовые алгоритмы подписи — рискованно: анализ 9 кандидатов NIST и почему ML-DSA уже лучший выбор

RSA и ECC — криптографические алгоритмы, на которые мы все полагались десятилетиями, — уязвимы перед атакой достаточно мощных квантовых компьютеров. Таких квантовых компьютеров пока не существует, но, похоже, они появятся раньше, чем ожидалось. К счастью, решение уже доступно: перейти на шифрование ML-KEM и подписи ML-DSA, которые разработаны для устойчивости к квантовым атакам. Они были стандартизированы в 2024 году Национальным институтом стандартов и технологий США (NIST) после восьмилетнего открытого международного конкурса.

Миграция на постквантовую криптографию сейчас в самом разгаре. На момент написания статьи большая часть трафика, обрабатываемого Cloudflare, уже использует шифрование ML-KEM и, таким образом, защищена от угрозы данным, исходящей от атак «собери сейчас, расшифруй потом». Но шифрование — лишь часть уравнения: чтобы быть полностью защищёнными от квантовых компьютеров, способных взломать классическую криптографию, мы стремимся развернуть постквантовые подписи для защиты систем аутентификации от несанкционированного доступа. Мы ставим целью 2029 год для полного обеспечения постквантовой безопасности Cloudflare.

ML-DSA — лучшая на сегодня универсальная схема постквантовой подписи — имеет свои недостатки: она гораздо большего размера в сети, и многие трюки, которые мы могли выполнять с RSA и ECC, просто невозможно реализовать с ML-DSA. На горизонте есть более совершенные постквантовые схемы подписи: в прошлом месяце NIST объявил о продвижении девяти постквантовых схем подписи в третий раунд «онбординга подписей». А проект стандарта для FN-DSA (ранее Falcon), выбранного из предыдущего конкурса, ожидается в ближайшее время.

Мы очень заинтересованы в прогрессе постквантовых алгоритмов подписи и писали о достижениях в 2021, 2022, 2024 и 2025 годах. В этой статье мы подробно расскажем вам о последних разработках.

Но сначала нужно разобраться со слоном в комнате: эти новые алгоритмы подписи не будут готовы к переходу на постквантовую криптографию — даже близко, как мы увидим позже. Проблема приближается слишком быстро, чтобы мы могли ждать. ML-DSA доступен уже сегодня, и он подойдёт для первой миграции. Как написал Эрик Рескорла в 2024 году:

На войну идут с теми алгоритмами, которые у вас есть, а не с теми, которые вы хотели бы иметь.

Тем не менее поиск лучших постквантовых алгоритмов подписи критически важен по нескольким причинам, и мы твёрдо верим, что это по-прежнему наилучшее использование ограниченных ресурсов NIST.

Давайте подробно рассмотрим алгоритмы подписи. После этого мы посмотрим на временные рамки их доступности и причины, по которым они всё ещё нужны.

В таблице ниже мы сравниваем алгоритмы-кандидаты, прошедшие в третий раунд (отмечены 🤔), с классическими алгоритмами, уязвимыми для квантовых атак (отмечены ❌), и постквантовыми алгоритмами, которые уже стандартизированы ( ✅) или будут в ближайшее время (📝). Каждый кандидат предлагает несколько вариантов. Мы перечисляем наиболее релевантные для TLS — протокола, используемого для защиты соединений в интернете. Чтобы изучить все варианты, загляните в зоопарк подписей Тома Виггерса.

Еще несколько замечаний по этой таблице: у большинства кандидатов есть несколько вариантов для каждого уровня безопасности. Мы показываем наиболее применимые варианты для TLS на уровне безопасности в 128 бит — золотом стандарте безопасности. Время CPU взято из sigzoo (sigzoo) в июне 2026 года, который собрал эти данные из документов второго раунда и последующих улучшений. Кандидатам разрешено вносить изменения для третьего раунда, что повлияет на эти цифры. Некоторые параметры улучшатся (как в скорости, так и в размере), тогда как другие ухудшатся для противодействия новым атакам. Проверьте sigzoo для получения последних цифр. Мы отметили подписи FN-DSA и SQIsign символом ⚠️️, так как обе сложно реализовать быстро и с защитой от атак по времени (timing side-channel). Подпись LMS отмечена символом ⚠️, так как безопасная подпись LMS требует хранения состояния между подписями, а указанное время подписания предполагает наличие кэша объемом 32 МБ. Вариант SLH-DSA 128-24 отмечен символом ⚠️️, так как он предназначен для создания менее 2²⁴ подписей.

Что сразу бросается в глаза, так это то, что уязвимый к квантовым атакам алгоритм подписи на эллиптических кривых Ed25519 является безусловно лучшим универсальным выбором (игнорируя его квантовую уязвимость): он имеет лучшие показатели практически по каждому метрику, включая размер открытого ключа, размер подписи и время подписания. Его превосходят только по времени верификации, но он более чем достаточно быстр для подавляющего большинства приложений.

Это сильно отличается от набора постквантовых алгоритмов. Вместо одного "вездесущего" алгоритма у нас есть примерно две категории схем: "специалисты", которые приближаются к нашим надежным подписям на эллиптических кривых по некоторым показателям, но проблематичны по другим, что делает их отличными в правильном сценарии развертывания. Затем есть "генералисты", такие как ML-DSA, которые не так хороши, как эллиптические кривые по всем показателям, но, насколько это касается недостатков, довольно сбалансированы.

Начнем со специалистов.

Если смотреть только на байты в сети, то SQIsign выглядит как почти идеальная замена криптографии на эллиптических кривых. С подписями размером 148 байт и открытыми ключами размером 65 байт он превосходит RSA-2048. К сожалению, бесплатных обедов не бывает: у SQIsign есть три слабых места. Во-первых, это самый сложный алгоритм из всех рассматриваемых. Во-вторых, создание и проверка подписи довольно медленные. Наконец, сложно реализовать создание подписи с защитой от атак по времени, и это также приводит к снижению производительности.

Пока это звучит не очень хорошо, но было еще хуже: когда мы оглянулись назад в 2024 году, не было ни одной реализации с защитой от атак по времени, а проверка подписи была в 20 раз медленнее. Кроме того, был достигнут значительный прогресс в упрощении схемы.

Несмотря на эти значительные улучшения, маловероятно, что (защищенное от побочных каналов) подписание будет достаточно быстрым в обозримом будущем для использования в типичных онлайн случаях, таких как рукопожатие TLS. Однако для офлайн случаев, таких как подписи CA или DNSSEC, где время проверки важнее времени подписания, SQIsign может найти применение.

Но тема, которую нам действительно следует обсудить, это безопасность. SQIsign основан на изогениях. Как известно, SIKE, другой алгоритм, основанный на изогениях, был серьезно взломан на позднем этапе первого конкурса NIST PQC, который стандартизировал ML-DSA. SIKE часто приводят в качестве наглядного примера того, что постквантовая криптография может внезапно сломаться. Это требует некоторого нюанса. Во-первых, уже были опасения по поводу безопасности SIKE, и в частности точек кручения, которые привели к взлому. Из-за этих опасений SIKE не был выбран для стандартизации, а был отложен на дополнительный раунд оценки, прежде чем был взломан. (Действительно, это пример того, как процесс NIST работает хорошо.) SQIsign не использует точки кручения, и нет подобных опасений, как для SIKE.

Еще одним заметным свойством безопасности является то, что наиболее известные атаки на SQIsign являются обычным перебором, как и в случае с классическими атаками на хорошо выбранные эллиптические кривые. Это сильно отличается от RSA, решеток и многомерных схем, где алгоритмы атак постепенно улучшались, подталкивая параметры к большим размерам подписей. Тем не менее, математика, лежащая в основе изогений, очень богата, и по сравнению с другими алгоритмами, здесь много математической поверхности для атак. Тем не менее, его безопасность кажется более надежной, чем у структурированных многомерных алгоритмов, которые мы обсудим позже.

SQIsign — это алгоритм с огромным потенциалом. Было бы жаль стандартизировать его слишком рано. Авторам мы хотели бы высказать следующие пожелания:

• В идеале время проверки должно быть еще больше уменьшено, даже если это будет достигнуто за счет времени подписания и размера подписи: подписи SQIsign уже достаточно малы, а время офлайн-подписания в любом случае имеет некоторый запас.

• Реализация с защитой от атак по времени должна быть стандартной, особенно если время подписания будет еще больше уменьшено, что соблазнит некоторые онлайн-приложения для подписания.

• Но прежде всего, мы хотим, чтобы SQIsign был упрощен.

UOV (несбалансированное масло и уксус) — это классический многомерный алгоритм подписи, первоначально предложенный в 1999 году. У него крошечные подписи: всего 96 байт. Плата? Огромный открытый ключ: 66 кБ. Это не поможет для сертификата сервера TLS, открытый ключ которого передается по сети при установке соединения, но это было бы полезно в случаях, когда открытый ключ распространяется заранее.

Возьмем для примера WebPKI. Типичный браузер доверяет примерно сотне корневых сертификатов и 30 журналам сертификационной прозрачности, открытые ключи которых при использовании UOV составят около 8 МБ.

Открытые ключи и подписи в типичном TLS-соединении.

Поскольку корневой сертификат передается клиентам внешним образом, одна из идей — использовать там подпись UOV. Но это не очевидное преимущество; из-за своего размера корневой сертификат UOV было бы непрактично использовать для перекрестной подписи, где корень используется как промежуточный. В то же время перекрестные подписи и промежуточные сертификаты становятся менее привлекательными в любом случае с более крупными постквантовыми подписями. Это стимулирует включать больше корневых сертификатов непосредственно в клиенты. Это снова будет в пользу UOV, но до определенной степени: если количество корневых сертификатов превысит тысячу, мы будем иметь дело с более чем 66 МБ ключевого материала, что составит значительную часть размера загрузки браузера (например, 90 МБ для Firefox 151.)

А как насчет безопасности? За прошедшие годы было предложено много вариантов UOV, которые используют некоторую дополнительную математическую структуру для уменьшения размера открытого ключа. Эти структурированные многомерные схемы имеют нестабильную репутацию: такие схемы, как Rainbow и GeMMS, были довольно серьезно взломаны. Важно отличать их от самого UOV, у которого гораздо лучшая репутация в плане безопасности, хотя и не идеальная.

Как и в случае со многими криптографическими схемами, в первые годы были проблемы роста, поскольку были обнаружены базовые атаки и ошибки в настройке параметров. Фактически, "U" в UOV является пережитком этого: оно означает несбалансированный, что является исправлением ошибки в настройке параметров схемы "масло и уксус" 1997 года, на которой основан UOV: в исходной схеме было равное количество переменных масла и уксуса в квадратичной системе уравнений, используемой в качестве открытого ключа, что, как оказалось, допускает атаку. Если вам интересно узнать о красочном названии: система уравнений содержит уксус x уксус и масло x уксус, но не содержит членов масло x масло. Это как винегрет с мелкими отдельными капельками масла. Вернемся к истории: с 2005 по 2020 год был тихий период для многомерных подписей: понимание UOV росло, но не было новых атак на типичные параметры.

Это изменилось в 2020 году с открытием атаки пересечения, которая основывалась на идеях оригинальной атаки на сбалансированное "масло и уксус". Атака пересечения удаляет около 30 бит безопасности из предложенного тогда 128-битного набора параметров. Значительный удар, но не фатальный: небольшая корректировка параметров полностью нейтрализует атаку с незначительным увеличением размера ключа и подписи.

Ещё большим шоком стала публикация 2025 года идеи использования клиньев для атаки на многомерные схемы. Первоначальное влияние на UOV было незначительным: всего несколько битов (опять же на уровне 128-битной безопасности). Опасение вызывало то, что эта идея возникла из ниоткуда, и было неясно, насколько далеко можно зайти с таким подходом. Это беспокойство частично оправдалось: идея клиньев оказалась очень плодотворной, и на её основе было построено несколько последующих атак, снизивших безопасность примерно на 15 битов. Однако также выяснилось, что атака клиньями и её обобщения можно рассматривать как частный случай атаки пересечением над усечёнными кольцами — таким образом, это гораздо более знакомый подход, чем мы думали. Опять же, эти атаки можно смягчить лишь незначительным увеличением размера ключей и подписей.

Что из всего этого следует? Такая история атак не редкость: за последние 25 лет решётки испытали гораздо более значительные снижения безопасности, хотя в последние годы этот процесс замедлился. Тем не менее, используемая в производстве криптография на решётках сегодня применяет консервативные наборы параметров, значительно превышающие 128-битный уровень, чтобы подстраховаться от будущего криптоанализа. Мы хотели бы сделать то же самое с UOV. Размер подписи растёт линейно с уровнем безопасности, составляя всего 260 байт даже на уровне 256-битной безопасности. К сожалению, размер открытого ключа зависит от уровня безопасности кубически: 446 кБ для 256-битного уровня. К счастью, UOV (как и большинство многомерных схем) обладает большой гибкостью при выборе наборов параметров на различных промежуточных уровнях безопасности.

UOV — это фундаментальная схема с узкими, но реальными сценариями использования. В будущем нам хотелось бы видеть набор параметров с небольшим запасом выше 128 бит, скажем, 160 бит, чтобы подстраховаться от будущих улучшений криптоанализа.

Как и SNOVA и MAYO, которые мы обсудим позже, QR-UOV является структурированной многомерной схемой: это вариант UOV, добавляющий больше структуры в открытый ключ для уменьшения его размера. Выгода скромная: в лучшем случае мы получаем открытые ключи размером 12 кБ, но проверка подписи для этого конкретного набора параметров непрактично медленная. Более реалистичные наборы параметров начинаются с открытых ключей размером 24 кБ.

Что касается безопасности, QR-UOV — единственная многомерная схема, которой не пришлось корректировать свои исходные параметры (первого раунда) в ответ на новые атаки. Это несколько удивительно, поскольку любая атака на UOV может быть применена и к QR-UOV. Объяснение в том, что атаки действительно применимы, но естественные параметры QR-UOV делают их неэффективными. С другой стороны, уже было известно несколько атак, использующих специфическую дополнительную структуру, которую добавляет QR-UOV: действительно, для некоторых наборов параметров атаки, специфичные для структуры, являются наилучшими. Это следует противопоставить MAYO, для которого не известно атак на дополнительную структуру, добавляемую MAYO. (Мы вернёмся к MAYO и SNOVA позже в этом посте.)

По сравнению с прошлым раундом, время подписи и проверки QR-UOV значительно улучшилось, но оно всё ещё относительно медленное. В целом, QR-UOV — трудная продажа: он добавляет эксплуатируемую структуру к UOV, не уменьшая размеры ключей до универсальных размеров.

Самыми первыми стандартизированными постквантовыми алгоритмами подписи являются основанные на хэше с состоянием LMS, HSS и XMSS^(MT). Они имеют очень маленькие открытые ключи, и для многих наборов параметров подписи намного меньше, чем у ML-DSA-44. К тому же их безопасность основана на безопасности хэшей, которые хорошо изучены и уже являются краеугольным камнем криптографии. Это делает алгоритмы подписи на основе хэша очень консервативным выбором, и нет необходимости подстраховываться более высокими уровнями безопасности.

Так в чём же подвох?

Их два. Главный — это поддержание одноимённого состояния. Эти схемы подписи на основе хэша с состоянием построены из одноразовых ключей подписи, которые собраны в деревья Меркла. Подписывающая сторона должна отслеживать, какие одноразовые ключи уже использованы, что может быть так же просто, как счётчик. Однако если подписывающая сторона ошибётся и случайно использует один и тот же одноразовый ключ дважды для разных сообщений, то любой сможет вероятно использовать эти две подписи для создания собственной подписи на любое сообщение. Нужно учитывать многое, чтобы правильно поддерживать состояние. Некоторые соображения: вы должны убедиться, что обновления записаны в хранилище до выдачи подписи; вы не хотите, чтобы старое состояние было восстановлено из резервной копии; и вы не можете экспортировать/импортировать закрытый ключ из одного места в другое без соглашения о том, как разделить или сохранить состояние. Состояние, как отметил Адам Лэнгли несколько лет назад, — это огромная пушка, стреляющая по ногам.

Другой недостаток — самые конкурентоспособные наборы параметров могут создавать лишь скромное количество подписей. Подписи размером 1112 байт (как указано в таблице выше) могут быть использованы для создания примерно миллиона подписей. Вы можете изучить компромиссы с помощью этого калькулятора.

В совокупности это оставляет очень маленькую нишу для подписей на основе хэша с состоянием: подписывающие стороны должны уметь поддерживать состояние; размер подписи должен быть реальной проблемой; и подписывающие стороны должны быть согласны с жёстким ограничением на количество подписей.

SLH-DSA — это подпись на основе хэша, которая не имеет низкого предела количества подписей и избегает проблемы поддержания состояния. Основная идея — сделать количество одноразовых ключей подписи настолько большим, что можно выбирать один случайным образом, не беспокоясь об использовании того же самого дважды, поскольку вероятность повторного выбора исчезающе мала. SLH-DSA немного эффективнее этого, заменяя одноразовый ключ подписи как строительный блок на ключ для нескольких подписей, где безопасность ухудшается плавно при случайном повторном использовании ключей. Однако это всё равно имеет свою цену. SLH-DSA имеет два варианта: один оптимизирован для малого размера подписи, а другой — для быстрой подписи. Оптимизированный по размеру вариант вовсе не мал — 8 кБ, а оптимизированный по скорости подписи вариант даже медленнее, чем SQIsign.

NIST предложил стандартизировать дополнительный набор параметров для SLH-DSA с гораздо более маленькими подписями, но который может быть использован для создания лишь около 16 миллионов подписей до снижения безопасности. При 3,8 кБ подписи всё ещё больше, чем у ML-DSA-44, но совокупный размер открытого ключа и подписи очень близок. Этот набор параметров был выбран для обеспечения быстрой проверки подписи за счёт времени подписания. Время подписания действительно очень плохое.

Так зачем вообще использовать SLH-DSA? Продающая точка — консервативная безопасность. Для долгосрочного доверенного ключа, который трудно заменить, это может иметь смысл, если приложение может выдержать большой размер подписи и медленную проверку стандартизированных вариантов или медленное время подписания недавно предложенного варианта. Есть ещё два предостережения. Во-первых, лучше настроить всё так, чтобы ключевые алгоритмы не были встроены намертво и могли быть заменены впоследствии. А во-вторых, в большинстве случаев системы (например, защищённые соединения с TLS) зависят не только от подписей, но и от согласования ключей. Не существует механизма согласования ключей на основе хэша, поэтому в любом случае нам приходится доверять чему-то менее консервативному, например решёткам.

Сравнивая числа, FN-DSA-512 (ранее Falcon) выглядит намного лучше, чем ML-DSA-44, почти по всем показателям: более быстрая проверка, меньший открытый ключ и гораздо меньшие подписи — 666 байт. Подписание в три раза медленнее, но всё ещё в 25 раз быстрее, чем RSA-2048. К тому же он уже выбран для становления FIPS 206. Так почему же мы не рассматриваем FN-DSA как универсальный алгоритм?

Это связано с тем, что безопасную реализацию подписи FN-DSA выполнить сложно. Самая известная острая грань FN-DSA заключается в том, что наиболее естественно и эффективно она реализуется с использованием аппаратно-ускоренной арифметики с плавающей запятой. Это впервые для криптографического стандарта. Одна из больших проблем заключается в том, что у нас мало опыта реализации быстрой арифметики с плавающей запятой безопасным с точки зрения побочных каналов способом. То, что мы знаем на данный момент, — это тонкая и не очень надежная вещь: безопасная реализация подписи FN-DSA с использованием блока операций с плавающей запятой (FPU) для одного процессора может оказаться небезопасной для другого. Вместо того чтобы полагаться на FPU, операции с плавающей запятой можно эмулировать. Это проще сделать правильно, но примерно в 20 раз медленнее, что делает ее примерно такой же медленной, как RSA-2048. Недавно был достигнут обнадеживающий прогресс в реализации подписи FN-DSA безопасным способом с использованием арифметики с фиксированной запятой, что намного быстрее, чем эмуляция плавающей запятой. Так что просто используйте это, и FN-DSA готова к использованию? Это предполагает уровень осведомленности, который может быть не оправдан. По слухам, на конференциях каждый раз, когда мы видели, как докладчик сравнивает постквантовые алгоритмы подписи, включая FN-DSA, в бенчмарках, они не могли ответить, использовалась ли эмуляция плавающей запятой.

Еще одно следствие использования чисел с плавающей запятой — сложность создания тестовых векторов для подписи. Просто один пример: результат a+(b+c) и (a+b)+c гарантированно близок, но не одинаков. Это означает, что для создания полезных тестовых векторов спецификация FN-DSA должна быть очень точной в отношении порядка операций с плавающей запятой. Другой пример — это a*b+c, которое можно вычислить в два этапа (умножение, затем сложение) или за один раз с помощью слитного умножения-сложения (FMA). Последний способ быстрее, но снова дает немного другой ответ, поскольку округление происходит только один раз. Не все процессоры поддерживают FMA, но для тех, которые поддерживают, компиляторы обычно автоматически используют FMA для повышения производительности. Также существуют математические оптимизации, которые вызывают проблемы. Например, эталонная реализация вычисляет значение (норму) более быстрым окольным путем с использованием теоремы Парсеваля. Математически ответ абсолютно одинаков, но, поскольку числа с плавающей запятой являются лишь приближением, результирующее значение незначительно отличается. Аналогично, безопасная реализация с фиксированной запятой дает немного другие результаты.

Почему это проблема? Это потому, что именно скромные тестовые векторы на практике выявляют большинство ошибок реализации. Другие, более совершенные методы, такие как формальная верификация, безусловно, выявят больше, но тестовые векторы трудно превзойти по простоте.

Еще одна удивительная острая грань из-за отсутствия фиксированной реализации заключается в следующем. Из двух детерминированных подписей, созданных немного разными реализациями с одним и тем же закрытым ключом, можно извлечь части этого закрытого ключа. FN-DSA не использует детерминированные подписи, вместо этого добавляя рандомизатор для предотвращения этого. Существует противоречие с тестированием: вам нужен детерминированный интерфейс для тестирования подписи, но вы не хотите, чтобы он использовался для создания реальных подписей.

Как бороться с неопределенностью в спецификации FN-DSA, несомненно, станет предметом обсуждения. Расхождение между реализациями может иметь и положительную сторону: NIST может решить генерировать тестовые векторы (CAVP) из реализации с фиксированной запятой. То, что более рискованная реализация с плавающей запятой не пройдет тестовые векторы, было бы особенностью, а не ошибкой, поскольку это направило бы реализации к более безопасной версии с фиксированной запятой!

Вы можете прочитать о некоторых других интересных острых гранях в этой записи в блоге. Отходя от деталей, главный вывод заключается в том, что FN-DSA — это сложная схема. Неудивительно, что NIST потребовалось пара лет (не считая текущего подвешенного состояния) только на написание проекта стандарта. Потребуется больше времени, чем обычно, чтобы выйти окончательному стандарту и чтобы криптографические библиотеки добавили поддержку. FN-DSA находится дальше, чем кажется. Мы сравним сроки позже в этой записи блога.

Если цифры все еще очень заманчивы, есть еще одна вещь, о которой вы должны знать: FN-DSA-512 параметризована для 128-битной безопасности по сравнению с щедрыми 160 битами ML-DSA-44. Если криптоанализ решеток улучшится, не будет среднего уровня безопасности: следующий шаг — сразу до FN-DSA-1024 с 256 битами. FN-DSA-1024 имеет вдвое больший размер ключа и подписи, а также время подписания и проверки по сравнению с FN-DSA-512. Подпись FN-DSA-1024 все еще вдвое меньше, чем у ML-DSA-44, но открытый ключ + подпись отличаются всего примерно на 20%.

В завершение обсуждения FN-DSA стоит подчеркнуть, что все трудности с FN-DSA находятся на стороне подписания: проверка подписи FN-DSA очень проста.

Теперь перейдем к алгоритмам, которые предназначены для замены ML-DSA общего назначения.

HAWK — любопытный случай. Во многих аспектах он похож на FN-DSA: структурированная решеточная схема «хеш-затем-подпись» с аналогичными размерами подписей и открытых ключей и отсутствующим средним уровнем безопасности. Основное преимущество HAWK перед FN-DSA заключается в том, что подписание происходит очень быстро и не использует арифметику с плавающей запятой, хотя это тоже не простой алгоритм. Это достигается ценой компромисса: HAWK основан на новом предположении безопасности — проблеме изоморфизма решеток (LIP). В 2024 году, через два года после появления HAWK, было обнаружено, что эта проблема легко решается в частном случае полностью вещественных числовых полей, которые не используются ни в HAWK, ни в какой-либо другой криптографии. В 2025 году эта атака была расширена на более широкий класс числовых полей. Это пока не применимо к HAWK, но становится все ближе. Новая статья, опубликованная в июне 2026 года, предполагает, что существует способ распространить атаку на HAWK. В статье была найдена ошибка, хотя пока неясно, насколько она фундаментальна для подхода. Тем не менее траектория вызывает беспокойство.

Даже игнорируя потенциальные атаки, HAWK сталкивается с некоторыми трудностями: его дополнительное предположение безопасности мешает ему вытеснить FN-DSA, но его практические преимущества (особенно учитывая отсутствие среднего уровня безопасности) уступают преимуществам структурированных многомерных кандидатов. Он также не увеличивает разнообразие предположений безопасности — результат, на который надеется NIST.

FAEST, MQOM и SDitH имеют схожую общую структуру. Их открытые ключи являются экземплярами некоторой сложной задачи, а секретные ключи — решениями.

• Открытый ключ FAEST — это AES-шифрование известного открытого текста с использованием секретного ключа.

• MQOM получил свое название от задачи многомерных квадратичных уравнений, которая тесно связана (но более консервативна) с криптографическими предположениями, лежащими в основе многомерных схем. Открытый ключ представляет собой систему квадратичных уравнений, а секретный ключ — решение этой системы уравнений.

• SDitH основан на сложности задачи декодирования синдрома для случайных линейных кодов. Эта задача связана с кодовыми схемами, представленными на первоначальный конкурс NIST, но они были исключены в третьем раунде.

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

Многие схемы подписи за кулисами являются такими доказательствами с нулевым разглашением, особенно ML-DSA, SQIsign и Ed25519. Почему мы не группируем их вместе со схемами доказательства знания?

Разница заключается в обобщаемости: доказательство с нулевым разглашением, используемое для ML-DSA, может доказать что-то только о конкретной задаче LWE, используемой в ML-DSA: доказательство использует математическую структуру в ключе. Существуют способы создания доказательств с нулевым разглашением с использованием решеток для любого общего утверждения, но эти системы доказательств сильно отличаются от ML-DSA и создавали бы довольно большие подписи порядка 50 кБ.

Напротив, система доказательств, используемая в FAEST, MQOM и SDitH, может использоваться для доказательства произвольных утверждений. Например, FAEST может быть модифицирована для использования сложной задачи MQOM. Это приводит к более эффективной схеме под названием KuMQuat. (Мы вернемся к некоторым показателям производительности позже.) И наоборот, MQOM может быть адаптирован для использования AES в качестве сложной задачи.

Эта гибкость хороша по двум причинам. Во-первых, она не требует какой-либо конкретной математической структуры в используемой сложной задаче, и поэтому мы можем выбрать очень консервативную задачу, такую как взлом AES. Некоторые задачи приводят к более эффективной подписи, чем другие, как мы видим на примере MQ, используемой в MQOM. MQ всё ещё является довольно консервативным предположением: она не содержит скрытого подпространства, используемого в UOV и, следовательно, в других многомерных подписях. К ней не применимы ни атаки пересечением, ни клиновидные атаки. Фактически, проблема MQ является NP-трудной. Для обеспечения безопасности всё равно необходимо выбрать правильный размер задачи, и хотя MQ изучается уже довольно давно, она, безусловно, не подвергалась такому же тщательному анализу, как развёрнутые алгоритмы, такие как AES.

Второе и более значительное преимущество заключается в том, что мы можем создавать гораздо больше, чем просто схему обычной подписи, на основе общей системы доказательств с нулевым разглашением: мы можем создавать слепые подписи и даже полноценные анонимные учётные данные.

Здесь стоит отметить ограничение: размер доказательств для всех трёх схем растёт линейно с размером доказываемого утверждения. Технически говоря, они не являются сжатыми (succinct), как STARKs и LaBRADOR, которые значительно превосходят их для больших утверждений. Это ещё один пример, когда иногда лучше выбрать подход, который не является асимптотически оптимальным.

Возвращаясь к преимуществам: помимо выбранной сложной задачи и безопасности хеш-функций, эти три схемы не требуют никаких дополнительных предположений о безопасности. Это делает FAEST таким же консервативным, как SLH-DSA.

Так в чём же разница, кроме выбранной сложной задачи? Эти схемы начинали совершенно по-разному, но с первого раунда они улучшались и сближались. Система доказательств в MQOM немного проще, чем в FAEST, но и работает она не так хорошо: KuMQuat (FAEST+MQ) превосходит MQOM.

Говоря о производительности, давайте начнём со сравнения с SLH-DSA. Все три схемы имеют варианты, которые превосходят любой стандартизированный набор параметров SLH-DSA, часто с хорошим отрывом. У SLH-DSA есть одно явное преимущество: процедура верификации проще в реализации.

Сравнение с ML-DSA-44 более интересно. Все схемы обеспечивают плавный компромисс между временем выполнения и размером подписи. Для иллюстрации приведены опубликованные компромиссы для KuMQuat (FAEST+MQ). Время верификации близко к времени подписания.

KuMQuat можно параметризовать так, чтобы получить несколько меньшие подписи, чем у ML-DSA-44, ценой большого времени подписания (и верификации). С другой стороны, он может иметь время подписания, схожее с ML-DSA-44, ценой больших подписей, хотя размер открытого ключа и подписи всё ещё сопоставим.

За эти годы эти схемы значительно улучшились, и мы ожидаем ещё некоторых улучшений. Хотя они не превзойдут ML-DSA так же dramatically, как некоторые другие рассматриваемые схемы, их консервативная безопасность и, особенно, потенциал для более широких применений, таких как анонимные учётные данные, делают их очень привлекательными. Чтобы продемонстрировать гибкость базовой системы доказательств с нулевым разглашением, мы хотели бы, чтобы каждая схема в этой категории представила цифры, показывающие, насколько хорошо они будут работать с другой базовой сложной задачей.

Как и QR-UOV, обсуждавшийся ранее, MAYO и SNOVA являются вариантами UOV, которые добавляют дополнительную структуру в открытый ключ для уменьшения его размера. MAYO и SNOVA используют два разных подхода: SNOVA делает агрессивные ставки для достижения наилучшей производительности, тогда как MAYO действует осторожно, придерживаясь консервативного дизайна.

SNOVA действительно впечатляет своей производительностью. Её основной набор параметров имеет подписи размером 248 байт (меньше, чем RSA-2048!) при открытом ключе всего 1 кБ. Она превосходит все другие постквантовые схемы по размеру открытого ключа и подписи и имеет отличное время выполнения.

Производительность MAYO тоже не вызывает насмешек. MAYO_one имеет лучшее время верификации, а её подписи размером 454 байта всё ещё меньше, чем у FN-DSA-512, HAWK-512 и RSA-4096. В сочетании с открытым ключом размером 1420 байт MAYO_one немного отстаёт от FN-DSA-512 и HAWK-512. Однако MAYO снова выходит вперёд, если мы запросим некоторый запас безопасности. FN-DSA и HAWK имеют пропущенный средний уровень безопасности, поэтому им нужно подниматься сразу до 256-битной безопасности, тогда как гранулярность MAYO позволяет добавить дополнительную безопасность за счёт небольшого увеличения размеров открытого ключа и подписи.

Если этого было недостаточно, и MAYO, и SNOVA допускают компромисс между размером подписи и открытого ключа. Таким образом, мы можем получить ещё меньшие подписи для открытых ключей, которые передаются заранее. Если довести до крайности, MAYO превращается в UOV.

До сих пор мы обсуждали производительность. А как насчёт безопасности? MAYO добавляет структуру "взбивания" (whipping) поверх UOV: любая атака на UOV будет работать и для MAYO, но могут быть атаки, специфичные для структуры взбивания MAYO. Пока не найдено атак на структуру взбивания, а значит, и на MAYO в частности. Худшее, что произошло, это то, что некоторые атаки на UOV затронули некоторые варианты MAYO сильнее, чем типичные наборы параметров UOV, из-за выбора параметров UOV, естественных для MAYO.

Это резко контрастирует с SNOVA. SNOVA неоднократно подвергалась серьёзным атакам на её специфическую структуру. В ответ команда SNOVA не просто настраивала параметры, но постоянно меняла саму структуру. Каждый раз они совершают скачок вперёд и предлагают новую SNOVA с ещё лучшей производительностью. Мы отметили это в прошлом году, и эта тенденция продолжилась, в то время как базовый дизайн MAYO стабилен.

Более того, структура, используемая SNOVA, может быть рассмотрена как особая форма отображения взбивания (whipping map), используемого в MAYO. Это означает, что любая атака, специфичная для MAYO, будет применима к SNOVA, но не наоборот.

В целом, мы наблюдаем большой прогресс в понимании многомерной безопасности. NIST написал, что ожидает дополнительный раунд перед стандартизацией многомерной схемы. Это кажется разумным. Нам неясно, будет ли SNOVA готова к тому времени, но MAYO, похоже, хорошо созрела.

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

Показательно взглянуть на ML-DSA.

После того как NIST выбрал Dilithium для становления ML-DSA, потребовался год на разработку проекта стандарта и ещё год на публикацию стандарта алгоритма. Стандарта алгоритма недостаточно: протоколам необходимо согласовать, как интегрировать ML-DSA. Для сертификатов это заняло ещё год. И это ещё не всё: программное обеспечение должно добавить поддержку ML-DSA и его интеграцию в протоколы.

Эти шаги не являются чисто последовательными: работа над программной реализацией ML-DSA началась до выхода финального стандарта. Кроме того, стандарты интеграции протоколов часто бывают «готовы» до того, как станут финальными. Например, использование ML-DSA в TLS уже завершено, но на момент написания статьи потребуется еще несколько месяцев, прежде чем будет опубликован соответствующий RFC. Примечательно, что OpenSSL опередил события и добавил поддержку ML-DSA до того, как были назначены кодовые точки IANA. Заметно отсутствует согласие по поводу того, какие гибридные подписи следует использовать в TLS (или вообще), для которых (на момент написания) не было назначено ни одной кодовой точки IANA.

Итак, что это означает для новых алгоритмов подписи? Если проект FN-DSA будет опубликован сегодня и будет развиваться с той же скоростью, что и ML-DSA, то, возможно, у нас будет некоторая ранняя программная поддержка в начале 2029 года, но без значительного развертывания. Учитывая время, которое потребовалось для написания проекта стандарта FN-DSA, вполне вероятно, что финальный стандарт, интеграция протоколов и программная поддержка также будут развиваться медленно. Мы не ожидаем, что FN-DSA станет широко доступен до 2033 года.

Прогресс в криптоанализе многомерных схем заставил NIST задуматься: они написали, что ожидают, что многомерным схемам потребуется как минимум еще один раунд продолжительностью около двух лет. С другой стороны, многомерные схемы относительно легко реализовать. Это означает, что мы можем увидеть многомерный стандарт NIST в 2031 году, а более широкую доступность продуктов — не ранее 2034 года.

NIST более уверен в безопасности SQIsign, чем в безопасности многомерных схем. Как и FN-DSA, SQIsign — сложная схема для стандартизации и реализации. В то же время достигнут значительный прогресс в упрощении SQIsign. Похоже, что SQIsign претерпит серьезные изменения в третьем раунде и, следовательно, потребует четвертого раунда оценки. В любом случае, широкое распространение до 2035 года маловероятно.

Как обсуждалось выше, HAWK занимает неудобную промежуточную позицию между FN-DSA и структурированными многомерными кандидатами. Если бы он был стандартизирован, что кажется маловероятным даже до недавнего прогресса в криптоанализе, мы бы не ожидали доступности продукта до 2034 года.

Остаются алгоритмы доказательства знания MQOM, SDitH и FAEST. Мы наблюдали значительные улучшения этих схем на протяжении раундов. Если такие темпы изменений сохранятся, потребуется еще один раунд, но если сейчас они стабильны, то алгоритм доказательства знания станет первым новым стандартом NIST, который увидит свет в 2030 году. Если он появится так рано, то, вероятно, не превзойдет ML-DSA кардинально. Тем не менее, он будет очень полезен для создания анонимных учетных данных и других примитивов, помимо подписей.

Итак, стоит ли вам ждать одну из этих подписей для миграции на постквантовую криптографию? Учитывая недавние достижения в квантовом оборудовании и программном обеспечении, мы считаем, что не можем позволить себе ждать. В Cloudflare мы стремимся к полной миграции к 2029 году. Ни одна из этих подписей не будет готова вовремя. Сроки большинства регуляторов варьируются от 2030 до 2035 года. Они не учитывали недавние достижения, и мы ожидаем, что они будут скорректированы. Мы видели это на примере указа президента США от июня 2026 года, установившего срок 2031 год. Даже если бы сроки не изменились, мы бы не советовали ждать.

Почему? Развертывание постквантовых подписей в 2034 году, чтобы уложиться в срок 2035 года, недостаточно. В системе любого разумного размера нельзя обновить все сразу. Потребуется переходный период, в течение которого поддерживаются как постквантовые, так и традиционные подписи. А поддержка обоих позволяет провести атаку понижения. Самый прямой способ предотвратить такое понижение — отключить классическую криптографию. Это займет время и, откровенно говоря, даже не является вариантом во многих достаточно распределенных системах, таких как WebPKI. Мы расскажем о том, как бороться с атаками понижения, в будущем посте в блоге. А пока вот немного информации для любознательных. В любом случае, борьба с атаками понижения потребует времени.

Кажется очевидным, что эти новые алгоритмы постквантовой подписи не будут готовы к использованию к моменту первой миграции. Так зачем вообще беспокоиться?

У нас было 50 лет, чтобы вплести криптографию с открытым ключом во все наше цифровое общество. У нас осталось несколько лет, чтобы сделать все это квантово-безопасным. Для большинства этих обновлений процедура ясна: внедрение постквантовой криптографии. Легче сказать, чем сделать: это монументальная задача. Но есть случаи, которые принципиально сложнее. В постквантовом мире не существует универсальной подписи, и есть случаи, когда размер ML-DSA является проблемой. При достаточных ресурсах и согласии заинтересованных сторон системы можно перепроектировать для хорошей работы с этими более крупными подписями. Действительно, благодаря ongoing реинжинирингу, постквантовый WebPKI формируется так, чтобы работать лучше, чем современный уязвимый для квантовых атак. Нереалистично ожидать, что это произойдет для каждой системы до того, как станет слишком поздно. Некоторым придется смириться с потерей производительности. Другим придется решать проблему безопасности иными способами, такими как ограничение доступа, туннелирование, усиление мониторинга или множество других мер, которые сами по себе дороги. Как только появятся более компактные постквантовые подписи, эти компенсирующие меры можно будет удалить, восстановив полную эффективность и безопасность.

Косвенное, но не менее важное преимущество продолжающегося конкурса NIST заключается в его помощи в продвижении постквантовой криптографии за пределы базовых примитивов: уязвимы для квантовых атак не только протоколы согласования ключей и подписи. Существует длинный хвост причудливых криптографических примитивов, используемых в производстве, таких как анонимные учетные данные, PAKE и пороговые подписи, назовем лишь некоторые. Для большинства из них постквантовые варианты либо недоступны, либо малоизучены. Для некоторых та же цель может быть достигнута без причудливой криптографии, но с прискорбной регрессией в тонких целях конфиденциальности. NIST не может проводить конкурс для определения постквантового стандарта для каждого из этих конкретных примитивов, но, к счастью, конкурс подписей оказал здесь огромную помощь.

Самый яркий пример — FAEST. Хотя он разработан как схема подписи, его базовый механизм (VOLEitH) может быть перепрофилирован в сочетании с многомерной схемой, такой как MAYO, для создания эффективного постквантового анонимного удостоверения. Без конкурса подписей VOLEitH не был бы так развит и проверен, как сегодня.

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