Пороговая ECDSA: многос​​тороннее подписание

Подписи ECDSA требуют вычислить случайный одноразовый параметр k, точку кривой R = k*G и подпись s = k^{-1}(h + r*x) mod n, где x — закрытый ключ, а r — x-координата точки R. Инверсия k и умножение на закрытый ключ делают ECDSA принципиально нелинейной, в отличие от подписей Schnorr, где ответ представляет собой простую линейную комбинацию. Эта нелинейность делает распределение вычисления между сторонами чрезвычайно сложным.

Протокол GG18 Дженнаро и Голдфедера (2018) стал первой практической двухсторонней и пороговой конструкцией ECDSA, безопасной без доверенного дилера. Ключевая идея — использовать гомоморфное шифрование Paillier для выполнения преобразования мультипликативного представления в аддитивное (MtA), необходимого для нелинейного вычисления ECDSA. GG18 обеспечивает безопасность на основе симуляции против статических получестных противников.

GG20 (Дженнаро и Голдфедера, 2020) улучшил GG18, доказав безопасность против злонамеренных противников без доверенной настройки. GG20 добавил доказательства с нулевым разглашением, чтобы гарантировать корректное соблюдение протокола каждой стороной. Эти доказательства не позволяют злонамеренной стороне сместить одноразовый параметр или подпись, чтобы извлечь информацию о долях ключей других сторон. GG20 стал основой для многих промышленных реализаций кошельков MPC.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) — самый современный пороговый протокол ECDSA. Он обеспечивает идентифицируемое прерывание: если протокол подписывания завершается сбоем из-за злонамеренных действий, протокол может определить, какой участник несёт за это ответственность. Это особенно важно для корпоративных внедрений, где имеет значение подотчётность. CGGMP21 реализован в популярных библиотеках MPC, включая tss-lib и multi-party-sig.

Основная проблема в пороговом ECDSA — вычислить произведение секретных долей, не раскрывая их. Преобразование MtA (из мультипликативной формы в аддитивную) преобразует произведение a*b долей двух участников в аддитивные доли: участник 1 получает alpha, а участник 2 — beta, так что alpha + beta = a*b. Это достигается с помощью шифрования Paillier: участник 1 шифрует a, участник 2 гомоморфно умножает шифртекст на b и добавляет случайное значение, после чего участник 1 расшифровывает результат и получает аддитивные доли.

Шифрование Paillier — это схема частично гомоморфного шифрования, поддерживающая сложение и умножение на открытый текст. Имея шифртекст Enc(a), любой участник может вычислить Enc(a*b) для известного b, не выполняя расшифрование. Это свойство позволяет реализовать протокол MtA: участник 1 генерирует пару ключей Paillier и отправляет Enc(k1) и Enc(x1) — доли одноразового значения и закрытого ключа. Участник 2 использует гомоморфные операции, чтобы вычислить свой вклад, не узнав k1 или x1.

Пороговое подписывание ECDSA обычно включает несколько раундов обмена данными. В GG20 есть фаза предварительной обработки (2 раунда), в которой формируются обязательства для одноразового значения и случайных маскирующих значений, а также онлайн-фаза подписывания (1 раунд), объединяющая частичные подписи. Предварительную обработку можно выполнить до того, как станет известно сообщение, сократив задержку онлайн-фазы до одного раунда. CGGMP21 дополнительно оптимизирует этот процесс.

Идентифицируемое прерывание означает, что при сбое порогового протокола подписывания — например, если участник отправил некорректное сообщение или не выполнил требования протокола, — честные участники могут криптографически определить, кто нарушил правила. Для этого на каждом шаге нужны доказательства с нулевым разглашением корректности вычислений. Без идентифицируемого прерывания злоумышленник может вызвать отказ в обслуживании, отказавшись завершать протокол, и при этом остаться неустановленным.

EdDSA (подписи на основе Schnorr над Ed25519) гораздо проще перевести в пороговую форму, чем ECDSA, поскольку подписи Schnorr линейны: ответ z = r + c*x представляет собой сумму аддитивных долей. FROST (гибкая пороговая схема Schnorr, оптимизированная по числу раундов), разработанная Komlo и Goldberg (2020), обеспечивает двухраундовое пороговое подписывание Schnorr без доверенной инициализации. IETF стандартизирует FROST (проект RFC) для использования в протоколах с сохранением конфиденциальности и криптовалютных кошельках.

Пороговый ECDSA требует больше вычислительных ресурсов, чем ECDSA с одним участником, из-за протокола MtA и доказательств с нулевым разглашением. Подписывание двумя участниками по GG20 занимает примерно 1–2 секунды на современном оборудовании; пороговое подписывание при большем n длится дольше из-за большего числа попарных выполнений MtA. Оптимизации CGGMP21 сокращают это время до нескольких сотен миллисекунд. Для криптовалютных транзакций, где важна задержка подписывания, такая производительность приемлема, хотя задержка всё же заметна.

Пороговый ECDSA применяется в институциональных финансовых организациях в больших масштабах. Fireblocks использует пороговый ECDSA на основе GG20, обеспечивая защиту транзакций общим объёмом свыше 4 трлн долларов. Coinbase Prime использует хранение активов на основе MPC и пороговых подписей. Qredo и Copper.co предлагают пороговый ECDSA для управления институциональными активами. Библиотека tss-lib для Go, используемая Binance, и multi-party-sig, используемая Coinbase, — это основные реализации с открытым исходным кодом.

Какую роль играет гомоморфное шифрование Paillier в пороговом ECDSA?

Пороговый ECDSA позволяет t участникам подписывать сообщения, не зная полного ключа. Нелинейная структура ECDSA требует преобразования MtA с использованием гомоморфного шифрования Paillier. GG18 положил начало этому подходу, GG20 добавил защиту от злонамеренных действий, а CGGMP21 — идентифицируемое прерывание. Для EdDSA/Schnorr проще построить пороговую схему с помощью FROST (2 раунда, без доверенной инициализации). Промышленные решения Fireblocks и Coinbase обеспечивают защиту активов на триллионы долларов.