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

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

В общем виде задача ставится следующим образом. Есть N участников, которые хотят сделать так, чтобы любые t из них имели возможность создавать совместные подписи от лица сразу всего сообщества. При этом меньшее количество, решивших что-то подписать, не могло бы это сделать. Число t называется порогом, а сама подпись — пороговой.

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

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

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

Таким образом, схема пороговой подписи (Threshold Signature Scheme, TSS) — это набор из двух протоколов ThreshKeyGen и ThreshSig, представляющих из себя инструкции по взаимодействию сторон с целью в первом случае создать необходимую пару ключей, а во втором — пороговую подпись. Для проверки подписей, созданных алгоритмом ThreshSig, используется уже знакомый нам обычный алгоритм Ver.

Протокол Threshold ECDSA

Протокол Threshold ECDSA — это реализация схемы пороговой подписи на основе алгоритма ECDSA. Поэтому, как и в ECDSA, здесь заранее фиксируется пять базовых начальных параметров: конкретная эллиптическая кривая, простое число n, точка G на кривой, такая что n является ее порядком, и два параметра, связанных с модульной арифметикой.

Протокол создания ключей ThreshKeyGen

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

составляют (t, N)—пороговое разделение ключа sk. Это означает, что исходный ключ можно восстановить, зная любые t частей, но при этом любого меньшего их числа для восстановления недостаточно.

Вначале каждый участник выбирает по случайному числу uᵢ. Секретный ключ sk определяется как условная сумма этих чисел:

Условная, потому что в таком виде никто не может ее посчитать (никто не знает сразу все значения uᵢ).

Публичный ключ pk, как и в обычном алгоритме KeyGen, определяется соотношением pk=sk ∙ G. Только теперь его вычисление происходит по частям. Каждый участник сперва находит свою точку Qᵢ=uᵢ ∙ G, затем отправляет ее остальным. Далее, имея у себя все точки

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

Таким образом, у участников уже создана пара ключей. Однако части uᵢ секретного ключа sk плохие — они не обладают тем свойством, что зная хотя бы t из них, ключ sk можно восстановить. Части uᵢ были просто первым необходимым этапом: с их помощью ключ sk был определен. Теперь же ключ sk нужно разделить по-другому, чтобы это разделение обладало пороговым свойством.

Здесь участники прибегают к использованию дополнительного протокола Feldman's VSS (Feldman’s Verifiable Secret Sharing). Этот протокол состоит из трех шагов.

1. На первом шаге каждый участник с помощью специального алгоритма делит свое число uᵢ на n частей, так, чтобы по любым t полученным кусочкам число uᵢ однозначно восстанавливалось.

2. На втором шаге каждый участник отсылает получившиеся части числа uᵢ остальным: каждому по одной части. При этом одна часть остается у участника. 

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

После этих пересылок у каждого участника окажется n чисел. Одно было изначально — собственный кусочек числа uᵢ, полученный на первом шаге протокола Feldman's VSS. Остальные были получены от других. Свою финальную часть секретного ключа sk каждый участник получает из этих чисел просто их суммированием.

Протокол создания подписи ThreshSig

Протокол создания подписи ThreshSig предполагает участие уже не n сторон, а t, поскольку этого количества должно быть достаточно, чтобы успешно создать пороговую подпись. Дополнительным входным параметром протокола является число m — хеш подписываемого сообщения. 

За основу берется обычный алгоритм Sig ECDSA. Главное отличие заключается в том, что теперь подпись вычисляется не напрямую, а по частям.

Каждый участник вычисляет свой кусочек подписи с использованием своей части секретного ключа sk. Затем эти кусочки собираются вместе и формируется финальная подпись (r, s). Сборка конечной подписи — это сумма подписей, которые создали участники.

Использованная литература

Rosario Gennaro, Steven Goldfeder, “Fast Multiparty Threshold ECDSA with Fast Trustless Setup”

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