Как Биткоин может противостоять квантовым компьютерам? Сравнение трех схем подписи на решетках

Автор оригинала: команда Blockstream

Компиляция оригинала: Saoirse, Foresight News

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

Цифровые подписи являются основным механизмом авторизации транзакций Биткоина, и используемые для этого подписи Schnorr и ECDSA имеют чрезвычайно низкую стоимость. В 1994 году Шор доказал, что достаточно мощный квантовый компьютер может взломать оба типа подписей. Хотя ведутся споры о том, когда такие машины станут доступны, нам необходимо разработать жизнеспособный план развертывания постквантовых подписей до того, как проблема реально возникнет.

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

В этом отчете изучаются три схемы: Dilithium, Falcon и Hawk. Для читателей, не знакомых с криптографией на решетках, мы объясняем обоснование дизайна каждой схемы, даем полное описание алгоритма и анализируем их с точки зрения безопасности, производительности и практического развертывания (например, деривации ключей кошелька). Какие из трех схем действительно могут быть развернуты в блокчейне Биткоина?

Критерии оценки

Биткоин имеет свои ограничения при выборе схемы подписи, и данная оценка сосредоточена на четырех основных критериях:

• Стоимость в цепочке: Одним из наиболее важных показателей является общий размер открытых ключей и подписей. Когда выход тратится, и открытый ключ, и подпись записываются в цепочку, и полные узлы должны загружать и хранить каждый байт. Накладные расходы на верификацию не менее критичны: каждая подпись проверяется всеми узлами сети, и медленная верификация создаст нагрузку на всю сеть.
• Сложность реализации: Возможность безопасной реализации схемы имеет решающее значение. Если конструкция требует арифметики с плавающей запятой или деликатной выборки по Гауссу, ошибка реализации или атака по побочному каналу, такая как анализ времени выполнения, может привести к утечке ключа. Для обеспечения плавной миграции сложность реализации является фактором, который нельзя игнорировать.
• Риск развертывания: При фактической интеграции в Биткоин возникают различные практические препятствия: выбор хеш-функции на уровне консенсуса (большинство кандидатов используют SHAKE, тогда как Биткоин использует SHA-256), воспроизводимость результатов подписи на разных платформах и соответствие процедуры подписи ограничениям памяти аппаратных кошельков.
• Потенциал развития: Подавляющее большинство кошельков Биткоина используют иерархический детерминированный механизм BIP-32: из одного мастер-открытого ключа можно вывести бесконечное количество дочерних открытых ключей без доступа к закрытому ключу. В настоящее время ни одна стандартизированная постквантовая схема подписи не поддерживает эту функцию изначально, поэтому мы изучаем стоимость добавления этой возможности; мы также рассматриваем различные нестандартные варианты схем, которые могут дать дополнительные преимущества.

Какой уровень безопасности следует выбрать?

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

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

Основные популярные продукты сделали такой же вывод. Протокол Apple iMessage PQ3 напрямую отбрасывает параметры решеток уровня 1 и использует параметры уровней 3 и 5; Cloudflare использует ML-KEM-768 (уровень 3) в своем постквантовом развертывании TLS, заявляя, что хотя уровень 1 в настоящее время кажется безопасным, необходимо зарезервировать запас безопасности на десятилетия будущего криптоанализа. Горизонт безопасности Биткоина еще длиннее, чем у обоих.

Повышение уровня безопасности имеет свою цену. Например, переход Dilithium с уровня 2 на уровень 3 увеличивает общий размер примерно на 1,5 килобайта. В отчете сравниваются наборы параметров на всех уровнях безопасности, что позволяет читателям самостоятельно взвесить компромиссы. Случай Hawk доказывает, что консервативные соображения безопасности не являются чисто теоретическими.

Подробный анализ схем-кандидатов

Dilithium: простая конструкция

Dilithium, стандартизированный NIST как ML-DSA в FIPS 204, переносит парадигму «обязательство-вызов-ответ» подписей Schnorr на арифметику модульных решеток.

Его главная особенность — простота. Все операции в Dilithium являются целочисленными: операции с кольцами, умножение матрицы на вектор, хеширование и округление. Нет арифметики с плавающей запятой и нет дискретной выборки по Гауссу. Легче писать безопасные реализации с постоянным временем выполнения. Это также наиболее широко развернутый кандидат, уже интегрированный в OpenSSL, BoringSSL, AWS-LC и Apple CryptoKit.

Компромисс — больший размер. На уровне безопасности 3 ML-DSA-65 имеет открытый ключ 1952 байта и подпись 3309 байт, всего 5261 байт, что примерно в 55 раз больше общего размера нативного открытого/закрытого ключа и подписи Биткоина, что делает его самым крупным из трех схем на том же уровне безопасности.

Для Биткоина наиболее ценным аспектом Dilithium является то, что это единственная из трех схем, которая приближается к реализации деривации ключей в стиле BIP-32. Конструкция с рерандомизируемым ключом DilithiumRK может генерировать дочерние ключи из родительских, используя только открытую информацию. В отчете анализируются три варианта, включая предложенный нами DilithiumRKS, где логика деривации полностью находится в программном обеспечении кошелька, а цепочке требуется только стандартный верификатор для обработки обычных подписей ML-DSA. Однако ни один из трех не готов к производственному использованию: два варианта требуют модификации верификатора, а сам DilithiumRKS не имеет полного доказательства неподделываемости; все схемы полагаются на общую для всей сети матрицу, что формально безопасно в рамках предположения Module-LWE, но связывает безопасность всех ключей с одним экземпляром. Мы считаем, что деривация открытых ключей на основе Dilithium в настоящее время является лишь доказательством концепции и не может быть развернута на практике.

Falcon: компактная схема

Falcon, выбранный NIST и стандартизированный как FN-DSA, является самой компактной из трех схем. На уровне безопасности 1 Falcon-512 имеет суммарный размер открытого ключа и подписи 1563 байта; на уровне 5 Falcon-1024 в сумме составляет 3073 байта. Falcon-1024 с более высоким запасом безопасности даже меньше, чем Dilithium уровня 3.

Falcon использует иной подход, чем Dilithium: парадигму «хешируй и подписывай» на основе решеток NTRU. Закрытый ключ подписывающего — это короткий базис решетки; сообщение хешируется в точку пространства, и подписывающий использует короткий базис, чтобы найти вектор решетки, близкий к этой точке. Точка и близлежащий вектор вместе образуют подпись; верификация лишь проверяет, что вектор принадлежит решетке и находится достаточно близко. Сложность реализации заключается в том, чтобы найти вектор, не раскрывая информацию о базисе. Ранние схемы GGH и NTRUSign напрямую выбирали близлежащие точки решетки, утекая некоторую геометрическую информацию с каждой подписью. Falcon принимает структуру GPV, выбирая близлежащие векторы из гауссова распределения, что доказуемо делает выборку независимой от базиса, устраняя риск утечки, но сложность реализации сэмплера значительно возрастает.

Сэмплер является инженерной слабостью Falcon. Он работает в комплексной области Фурье и требует вычислений с плавающей запятой. Разные процессоры, компиляторы и параметры оптимизации компиляции могут привести к несогласованным результатам с плавающей запятой. Это не только проблема совместимости, но и проблема безопасности: доказательство безопасности GPV требует, чтобы подписывающий никогда не выдавал два разных коротких вектора для одного и того же дайджеста; если подпись становится детерминированной, различия в округлении с плавающей запятой, вызванные платформой, нарушат это условие. Существует жизнеспособное решение: детерминированный Falcon может заменить аппаратную плавающую запятую целочисленной эмуляцией, создавая идентичные подписи на всех платформах. Цена — примерно 15-кратное замедление скорости подписи и примерно 2-кратное замедление генерации ключей.

Важно, что верификация не затрагивается: верификация Falcon полностью целочисленная, детерминированная и самая быстрая среди кандидатов. Это асимметричное свойство очень дружественно к Биткоину: подпись выполняется один раз кошельком при трате транзакции, тогда как каждая подпись проверяется всеми полными узлами сети. 15-кратное замедление подписи — это низкочастотная стоимость, а взамен мы получаем кросс-платформенную воспроизводимость и целочисленную арифметику, что мы считаем разумным компромиссом. Таким образом, проблема с плавающей запятой — это препятствие, которое можно решить инженерными средствами, а не фатальный недостаток.

Следует отметить два момента: из-за структурных ограничений у Falcon нет параметров уровня 3; нужно выбирать либо уровень 1, либо уровень 5. Исходя из соображений запаса безопасности, мы рекомендуем Falcon-1024. Во-вторых, подпись потребляет большой объем памяти: сэмплер для набора параметров 1024 опирается на предварительно вычисленное дерево, занимающее около 90 килобайт памяти. Аппаратные кошельки могут динамически перестраивать дерево ветвь за ветвью, снижая использование памяти до 16 килобайт, но время подписи удваивается. Более медленная подпись на аппаратных устройствах — это реальная стоимость, но все же приемлемая.

Hawk: неудачная схема

Hawk стремился объединить преимущества двух других схем: подписи Hawk-512 составляют всего 555 байт, меньше, чем у Falcon; подпись полностью целочисленная, с минимальным объемом памяти всего 6 килобайт. Это был также единственный кандидат на решетках, оставшийся в третьем раунде дополнительного конкурса подписей NIST, и в отчете этой схеме уделено значительное место.

Компромисс заключается в предположениях безопасности. Он не опирается на проблемы NTRU или SIS, которые подвергались десятилетиям криптоанализа, а на проблему изоморфизма решеток и предположение one-more-SVP, оба из которых имеют относительно короткую историю исследований.

Незадолго до финализации отчета Стразницкас и Вайс из Anthropic обнаружили структурный недостаток в конструкции решетки Hawk: размерность проблемы SVP, которую фактически необходимо решить для восстановления ключа, составляет лишь половину от задуманной разработчиками. Биты безопасности восстановления ключа для кандидатных наборов параметров были значительно ослаблены. Исследователи выполнили полную сквозную атаку восстановления ключа на тестовый параметр HAWK-256, используемый для криптоанализа; даже под атакой формально предложенные HAWK-512 и HAWK-1024 остаются практически невзламываемыми. Команда Hawk подтвердила действительность атаки и отозвала схему из процесса NIST; команда заявила, что если бы уязвимость была исправлена удвоением параметров, исходное преимущество Hawk в размере полностью исчезло бы.

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

Сравнительная таблица схем

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

Множество препятствий остается для развертывания

У Falcon отсутствует пригодная схема деривации ключей. Единственная публично доступная схема деривации Falcon в стиле BIP-32 рерандомизирует базис закрытого ключа, что приводит к резкому увеличению верхней границы нормы подписи, и подписи в цепочке раздуваются примерно до 23,7 килобайта. Более того, параметры схемы не удовлетворяют ее собственным условиям безопасности, и исправление этой проблемы еще больше увеличит размер. В настоящее время нет жизнеспособной реализации деривации открытых ключей Falcon, что также является самой ценной открытой проблемой, выявленной в отчете.

Стандарт Falcon еще не финализирован. Хотя NIST выбрал Falcon, черновик FN-DSA официально не выпущен. Только после завершения стандартизации у нас будут аудированные реализации, тестовые векторы и поддержка на аппаратном уровне. Широкое внедрение может снизить риск и сложность интеграции в уровень консенсуса Биткоина. Мы рекомендуем дождаться официального выпуска FN-DSA; до тех пор Falcon остается в состоянии неопределенности.

Вариант Falcon-WS: Этот вариант ослабляет внутренние параметры и полагается на выборку с отклонением для компенсации, сжимая общий размер до 1114 байт на уровне 1 и 2387 байт на уровне 5, дополнительно уменьшая размер по сравнению с исходным Falcon. Это направление имеет исследовательскую ценность, но не будет включено в официальный стандарт и требует дополнительной криптоаналитической проверки. Существующие исследования выявили недостатки в доказательствах сильной неподделываемости его производных схем (обычная неподделываемость не затрагивается).

Появятся ли лучшие схемы в будущем? Помимо вышеуказанных схем, семейство Фиата-Шамира восходит к BLISS 2013 года. Последний результат Гартнера на CRYPTO 2025, основанный на зрелых предположениях, имеет размеры, сравнимые с Falcon. Коренная причина трудности инженерной реализации этого семейства заключается в безопасности реализации: BLISS был взломан атаками по побочным каналам из-за непостоянной по времени выборки по Гауссу; последующие схемы не полностью решили эту проблему, и последний результат также предполагает, что защита этапа выборки еще сложнее. Пока проблема не решена, такие схемы привлекательны только теоретически и не подходят для развертывания.

Подписи на решетках и на основе хешей могут дополнять друг друга. Подписи на решетках могут служить компонентами гибридных схем. Например, в SHRINCS путь восстановления без сохранения состояния в настоящее время использует подписи SPHINCS+ размером в несколько килобайт; замена их подписями Falcon (или Falcon-WS) будет меньше и быстрее в верификации, значительно снижая накладные расходы редкого пути восстановления без влияния на повседневный путь использования.

Выводы исследования

Рейтинг кандидатов на решетках ясен: Hawk вышел из конкурса после атаки команды Anthropic; Dilithium имеет наименьшую сложность реализации и является единственной схемой с исследовательской базой для деривации ключей, но его размер не дружественен к стоимости в цепочке Биткоина; Falcon сочетает компактный размер, быструю верификацию и зрелые предположения безопасности; его главный недостаток — арифметика с плавающей запятой на стороне подписи — уже имеет жизнеспособное инженерное решение. Если бы нам пришлось выбирать схему подписи на решетках для Биткоина сегодня, мы бы выбрали Falcon-1024.

На данный момент наша точка зрения согласуется с отчетом о подписях на основе хешей: консервативный краткосрочный маршрут остается за подписями на основе хешей, с наиболее зрелыми предположениями безопасности и наименьшим риском, подходящими в качестве переходной схемы. Как только FN-DSA будет официально финализирован, со стабильными спецификациями, аудированными кодовыми базами и поддержкой аппаратных кошельков, Falcon принесет значительные улучшения по сравнению с чисто хеш-подписями; также может быть принято гибридное развертывание, позволяющее двум системам подписи дополнять друг друга.