Пороговые подписи

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

Что такое схема пороговой подписи?

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

Напомним, что схема подписи с одним участником обеспечивает свойство безопасности — невозможность подделки: если подпись выдана, то с подавляющей вероятностью она была сгенерирована субъектом, обладающим закрытым ключом, соответствующим открытому ключу. Кроме того, на концептуальном уровне схема пороговой подписи обеспечивает два свойства безопасности: 1) избыточность и 2) устойчивость к компрометации. Схема пороговой подписи обеспечивает устойчивость в том смысле, что она позволяет пороговому числу t участников из n возможных подписать сообщение под совместным открытым ключом. Она также обеспечивает устойчивость к компрометации: если не более чем (t - 1) участников будут скомпрометированы (например, их закрытые ключи украдены), то схема пороговой подписи остаётся неподделываемой.

Более детально, схема пороговой подписи состоит из n потенциальных подписантов. На этапе генерации ключей каждому участнику выдаётся доля секретного ключа, соответствующая части единого совместного секретного ключа (который неизвестен ни одному участнику полностью). Набор подписантов представлен единым совместным открытым ключом. Затем, на этапе подписания, коалиция как минимум t участников принимает участие в протоколе подписания. Результатом этого протокола является совместная подпись сообщения. Аналогично схеме подписи с одним участником, совместная подпись является корректной относительно совместного открытого ключа.

Как выполняется генерация ключей для пороговых подписей?

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

Доверенный распределитель

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

Распределённая генерация ключей

Чтобы исключить единую точку отказа, генерация ключей может быть распределена в рамках многопартийного протокола, где каждому участнику доверяют в равной степени. Такой многопартийный протокол для генерации ключевого материала в схеме пороговой подписи называется протоколом распределённой генерации ключей (Distributed Key Generation, DKG). В общих чертах многие DKG-протоколы предполагают, что каждый участник выполняет экземпляр операции доверенного распределителя, а затем на заключительном этапе выполняется «агрегация» ключевого материала из всех экземпляров в единый открытый ключ и набор долей секретного ключа.

Следует отметить, что в DKG-сценарии ни один участник не узнаёт итоговый секретный ключ; каждый получает только открытый ключ и свою соответствующую долю секретного ключа. Таким образом, пока менее чем (t - 1) участников будут скомпрометированы, ни одна сторона не сможет восстановить общий секретный ключ.

Существует несколько хорошо зарекомендовавших себя DKG-протоколов для схем подписей на основе дискретного логарифма [1]. Как правило, протоколы требуют, чтобы участники были аутентифицированы посредством существующей инфраструктуры открытых ключей и обменивались сообщениями через широковещательный канал, который предполагается аутентифицированным и согласованным. На практике многие реализации используют техники «эхо‑широковещания» для обеспечения согласованности представлений участников [2]. Кроме того, может использоваться роль «координатора» для организации обмена сообщениями между участниками и снижения сложности точечных коммуникаций.

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

Как используются пороговые подписи на практике?

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

Хотя предыдущий пример можно реализовать и в однопользовательской схеме путём копирования закрытого ключа на несколько машин, это увеличивает поверхность атаки и вероятность компрометации ключа. Здесь вступает в силу второе свойство пороговых подписей. Для схемы пороговой подписи, даже если (t - 1) машин, содержащих (t - 1) долей секретного ключа, будут скомпрометированы, эти (t - 1) вредоносные машины не смогут выдать корректную подпись без привлечения ещё одной незакомпрометированной машины. Поскольку схема пороговой подписи требует участия t подписантов, она защищает от возможных компрометаций вплоть до t участников.

Сценарии, где пороговые подписи особенно полезны, связаны с высоко доверенными центрами подписания. Например:

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

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

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

4. Подписание программных пакетов: При распространении программных пакетов и обновлений возможно подписывать код или бинарный файл сертификатом, чтобы гарантировать его неизменность перед установкой на устройство клиента. Для распределения доверия к ключу подписи может использоваться схема пороговой подписи, разделяющая ключ между несколькими машинами‑подписантами.

Пример: пороговый алгоритм цифровой подписи на эллиптических кривых и пороговый BLS

Идеальной характеристикой пороговых подписей является их совместимость с существующими алгоритмами проверки подписей для одного участника. Далее мы рассмотрим два практических примера пороговых подписей.

FROST: гибкие пороговые подписи Шнорра с оптимизацией по числу раундов

Одним из простых практических примеров является FROST (Flexible Round-Optimized Schnorr Threshold Signatures) [3], который позволяет выдавать подпись Шнорра с использованием порогового числа подписантов. Кроме того, поскольку алгоритм цифровой подписи на кривых Эдвардса (EdDSA) является вариантом подписи Шнорра, FROST может формировать подписи, совместимые с алгоритмом проверки EdDSA.

Протокол подписания в FROST может выполняться либо в два онлайн‑раунда, либо в один онлайн‑раунд после предварительной пакетной обработки. FROST защищает от класса атак на параллельность [4], которые ранее не учитывались в пороговых схемах подписи Шнорра. Такие атаки возможны, когда подписанты открывают множество сеансов подписания параллельно, предоставляя противнику возможность выбирать, какие сеансы завершить, а какие прервать.

Открытые ключи в FROST идентичны открытым ключам EdDSA. Однако каждый подписант получает долю закрытого ключа по схеме разделения секрета Шамира. Подписи могут формироваться либо с использованием двухраундового интерактивного онлайн‑протокола, либо однораундового неинтерактивного протокола после пакетной предварительной обработки. Участники могут обмениваться сообщениями в широковещательном режиме, либо может использоваться централизованный недоверенный координатор для маршрутизации сообщений. Итоговая подпись идентична подписи EdDSA с одним участником, и её проверка выполняется тем же алгоритмом EdDSA.

FROST не является устойчивым: если хотя бы один подписант не предоставит свою долю подписи, протокол необходимо запускать заново. Для некоторых приложений вероятность такого сбоя минимальна, например, когда участвует небольшое число подписантов. Однако для других сценариев, где число подписантов велико, устойчивость является желательным свойством. В этом случае протокол ROAST (Asynchronous Schnorr Threshold Signatures) [5] используется как надстройка над FROST, обеспечивая эффективную устойчивость при трактовке базовой схемы подписи как «чёрного ящика».

FROST был специфицирован в информационном проекте Internet Engineering Task Force и близок к завершению. Для тех, кто заинтересован во внедрении FROST, это является хорошей отправной точкой.

Пороговый BLS

Схема подписи BLS [6] позволяет реализовать ещё более эффективную пороговую схему [7]. Генерация ключей для порогового BLS аналогична FROST: открытый ключ остаётся таким же, как в однопользовательской схеме BLS, а каждый подписант получает долю закрытого ключа по схеме разделения секрета Шамира.

Подписание в пороговом BLS, однако, может выполняться в одном неинтерактивном раунде коммуникации. Каждый участник фактически выполняет операцию подписи BLS для одного участника, но дополнительно добавляет коэффициент Лагранжа, позволяющий интерполировать долю секрета по схеме Шамира. Итоговая подпись идентична подписи BLS для одного участника, и её проверка выполняется тем же алгоритмом BLS.

Примечательно, что пороговый BLS является устойчивым. Если какой‑либо участник не предоставит свою долю подписи, то при условии, что t участников ответят на запрос подписи для конкретного сообщения, корректная подпись может быть сформирована путём вычисления различных коэффициентов Лагранжа для данного подмножества.

В целом схема пороговой подписи обеспечивает два свойства безопасности: 1) избыточность и 2) устойчивость к компрометации.

Что учитывать на практике

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

Сколько подписантов выбирать

Прежде всего, одним из вопросов является количество необходимых участников подписания. Для некоторых приложений достаточно простой конфигурации «два из трёх», где t = 2 — число требуемых подписантов, а n = 3 — общее количество возможных подписантов. В такой конфигурации допускается компрометация одного участника, но не более. Подобная схема часто используется в криптовалютных кошельках.

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

Как выполнять резервное копирование долей ключа подписи

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

Как выполнять ротацию ключей

Ротация ключей является важной мерой многоуровневой защиты и помогает противостоять атакам на компрометацию. Преимуществом пороговых подписей является то, что доли секретного ключа подписи могут ротироваться при сохранении неизменным открытого ключа, что невозможно в схеме с одним подписантом. Такая особенность называется проактивной безопасностью. Ротация ключей подробно описана в предыдущей литературе [8] и реализована на практике.

Как управлять состоянием

Для многораундовых схем подписи, таких как FROST, подписанты должны генерировать новую случайность для каждой новой сессии подписания и хранить её в состоянии до завершения этой сессии. После выполнения финального раунда подписания крайне важно, чтобы подписанты удалили это состояние. Кроме того, необходимо, чтобы состояние не использовалось повторно в разных сессиях. Таким образом, разработчики должны обеспечить надёжное управление состоянием, что становится особенно сложной задачей при параллельном выполнении нескольких сессий подписания. Для обеспечения безопасности даже в условиях параллельности управление состоянием может осуществляться с использованием защищённого хранилища данных с механизмом блокировки.

Перспективные разработки

Наступает захватывающий период для пороговых подписей, и ожидается, что исследования и применение этих схем будут только расширяться. Одним из важных направлений является инициатива NIST [9] по формализации существующих схем пороговых подписей и продвижению процесса стандартизации. Этот процесс позволит создать конкретные стандарты для широкого спектра пороговых схем, включая как EdDSA, так и алгоритм цифровой подписи на эллиптических кривых (ECDSA).

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

Список литературы

1. Розарио Дженнаро, Станислав Ярецки, Хуго Кравчик, Тал Рабин. «Безопасная распределённая генерация ключей для криптосистем на основе дискретного логарифма». Журнал криптологии, т. 20, № 1, с. 51–83, 2007. doi: 10.1007/s00145-006-0347-3.

2. Шафи Голдвассер, Йехуда Линделл. «Безопасные многопартийные вычисления без соглашения». Журнал криптологии, т. 18, № 3, с. 247–287, 2005. doi: 10.1007/s00145-005-0319-z.

3. Крис Комло, Иан Голдберг. «FROST: гибкие пороговые подписи Шнорра с оптимизацией по числу раундов». В: Труды Международной конференции по выбранным областям криптографии, 2020, с. 34–65.

4. Фади Бенхамуда, Тома Лепуан, Йонас Лосс, Микеле Орру, Мария Райкова. «О (не)безопасности ROS». Журнал криптологии, т. 35, № 4, 2022, статья № 25. doi: 10.1007/s00145-022-09436-0.

5. Тим Руффинг, Винсент Ронге, Эрик Джин, Йохан Шнайдер-Бенш, Доминик Шрёдер. «ROAST: надёжные асинхронные пороговые подписи Шнорра». В: Труды конференции ACM SIGSAC по компьютерной и коммуникационной безопасности (CCS), 2022, с. 2551–2564. doi: 10.1145/3548606.3560583.

6. Дэн Бонэ, Бен Линн, Ховард Шахам. «Короткие подписи на основе сопряжения Вейля». Журнал криптологии, т. 17, № 4, с. 297–319, 2004. doi: 10.1007/s00145-004-0314-9.

7. Анна Болдырёва. «Пороговые подписи, мультиподписи и слепые подписи на основе схемы подписи группы gap-Diffie-Hellman». В: Public Key Cryptography, ред. Ю. Десмедт. Берлин, Гейдельберг: Springer, 2003, с. 31–46.

8. Томас Лэйнг, Дуглас Стинсон. «Обзор и уточнение восстанавливаемых пороговых схем». Журнал математической криптологии, т. 12, № 1, с. 57–81, 2018. doi: 10.1515/jmc-2017-0058.

9. Луис Брандау, Рене Перальта. «Первый призыв NIST к многопартийным пороговым схемам». Национальный институт стандартов и технологий, Гейтерсберг, США, 2023. [Онлайн]. Доступно по ссылке: https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8214C.ipd.pdf

10. Дэниел Коннолли, Крис Комло, Иан Голдберг, Кристофер Вуд. «Двухраундовые пороговые подписи Шнорра с FROST». IETF Datatracker, RFC 9591, июнь 2024. [Онлайн]. Доступно по ссылке: https://www.rfc-editor.org/rfc/rfc9591.html