*Примечание редактора: эта технология была опубликована на Международной конференции IEEE 2023 года по параллельной и распределенной обработке с приложениями, большим данным и облачным вычислениям, устойчивым вычислениям и коммуникациям, социальным вычислениям и сетям (ISPA/BDCloud/SocialCom/SustainCom). DOI: 10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00092*

# Введение

Li17 — самая быстрая и безопасная в отрасли подпись 2-2 ECDSA. CGGMP20 — самая безопасная и относительно быстрая пороговая подпись tn ECDSA в отрасли. В сфере хранения цифровых активов широко используются 2-3 пороговые подписи ECDSA. В этом случае сигнатуру Li17 2-2 нельзя использовать напрямую, и ее необходимо соответствующим образом изменить. В частности, вносятся следующие изменения: Алиса и Боб запускают протокол децентрализованной генерации ключей для генерации фрагментов закрытого ключа $a$ и $b$ соответственно, затем дважды запускают протокол обновления децентрализованного ключа для генерации $(a ', b')$; и $(a'', b'')$; Алиса конфиденциально отправляет $a'$ Кэрол, а Боб конфиденциально отправляет $b''$ Кэрол. Таким образом, Алиса и Боб используют сегментирование закрытого ключа $(a,b)$, Алиса и Кэрол используют сегментирование закрытого ключа $(a'', b'')$, а Боб и Кэрол используют сегментирование закрытого ключа $(a',b ')$, можно добиться подписи. Однако описанный выше процесс напрямую отправляет фрагменты секретного ключа. Если фрагменты секретного ключа утекли, ответственность не может быть отслежена, и нагрузка на хранилище увеличивается! С другой стороны, пороговая подпись CGGMP20 tn требует использования $t=2,n=3$. Однако сложность протокола CGGMP20 относительно высока, поэтому убить курицу большим ножом невозможно!

В этой статье, стоящей на плечах гигантов Li17, предлагается быстрая и безопасная пороговая подпись 2-n ECDSA. Протокол наследует безопасность и скорость подписей Li17 2-2.

В частности, в протоколе децентрализованной генерации ключей и протоколе обновления ключей порог строится на основе интерполяционного полинома Лагранжа для достижения пороговой подписи 2-n. Кроме того, на этапе предварительного подписания предварительно рассчитывается случайное сообщение; на этапе онлайн-подписи необходимо подписать только разницу между сообщением и случайным сообщением, тем самым повышая скорость этапа онлайн-подписи. Таким образом, пороговая подпись 2-n ECDSA в этой статье так же безопасна, как и протокол подписи Li17 2-2, а скорость подписи выше.

# 2-n пороговая подпись ECDSA

Инициализация: генератором группы эллиптических кривых $\mathbb{G}$ является $G$, а порядок — $\tilde{q}$.

## Протокол 1: децентрализованная генерация ключей

**Шаг 1:** Каждый пользователь $i$ генерирует свою пару ключей Пайе $({{N}_{i}},{{p}_{i}},{{q}_{i}} )$ .

Выберите случайное число ${{u}_{i}}\in [0, \tilde{q}-1]$ и вычислите точки эллиптической кривой следующим образом:

$${{U}_{i}}:={{u}_{i}}\cdot G.$$

Затем вычислите обещание и откройте обещание:

$$(KG{{C}_{i}},KG{{D}_{i}}):=\mathsf{Com}({{U}_{i}}).$$

Обязательство по широковещанию $KG{{C}_{i}}$ и открытый ключ Paillier ${{N}_{i}}$, сохранение случайного числа ${{u}_{i}}$, закрытый ключ Paillier ${ {p}_{i}},{{q}_{i}}$ и открытое обязательство $KGD_i$.

Обязательство по широковещанию $KG{{C}_{i}}$ и открытый ключ Paillier ${{N}_{i}}$, сохранение случайного числа ${{u}_{i}}$, закрытый ключ Paillier ${ {p}_{i}},{{q}_{i}}$ и открытое обязательство $KGD_i$.

**Шаг 2:** При получении обязательства $KG{{C}_{j}},j\ne i$ и открытого ключа Paillier ${{N}_{j}},j\ne i от других пользователей После $ пользователь $i$ передает свое открытое обязательство $KG{{D}_{i}}$ другим пользователям.

**Шаг 3:** Каждый пользователь $i$ проверяет правильность всех открытых обязательств, полученных от других пользователей.

Если он действителен, совместный открытый ключ рассчитывается следующим образом:

$$PK:=\sum\limits_{i=1}^{n}{U_i}.$$

Постройте **избыточность Лагранжа**: выберите случайное число $a_i\in [0,\tilde{q}-1]$ и постройте полином первого порядка:

$${{p}_{i}}(x)={{u}_{i}}+x\cdot a_i.$$

Сохраните ${{p}_{i}}(i)$ и тайно отправьте ${{p}_{i}}(j)$ другому пользователю $j$.

Вычислите **кортеж Фельдмана**:

$${{A}_{i}}:={{a}_{i}}\cdot G$$

Трансляция $A_i$.

**Шаг 4:** Каждый пользователь $i$ получает ${{p}_{j}}(i)$ и $\{{{A}_{j}}\},j, отправленные другими пользователями =1 ,...,n $, проверьте согласованность **кортежа Фельдмана**:

$${{p}_{j}}(i)\cdot G={{U}_{j}}+i\cdot {{A}_{j}}.$$

Рассчитайте фрагменты закрытого ключа и сегменты открытого ключа следующим образом:

$$\begin{выровнено}

& {{x}_{i}}:=\sum\limits_{j=1}^{n}{{{p}_{j}}(i)}\,\bmod \,\tilde{q} =sk+\sum\limits_{j=1}^{n}{(j\cdot {{a}_{j}})}\,\bmod \,\tilde{q}, \\

& {{X}_{i}}:={{x}_{i}}\cdot G. \\

\end{aligned}$$

Затем используйте zk-Schnorr, чтобы доказать, что он знает фрагмент секретного ключа ${{x}_{i}}$, и zk-Paillier-Blum, чтобы доказать, что ${{N}_{i}}$ является Пайе -Модуль Блюма.

Зашифруйте ${{x}_{i}}$, используя открытый ключ Paillier ${{N}_{i}}$

$${{c}_{key,i}}:=\mathsf{Enc}_{{{N}_{i}}}({{x}_{i}})$$

zk доказательство дальности действия

$$zk\left\{ {{x_i},{r_i}\left| \begin{array}{l}

{{c}_{key,i}} ={{(1+{{N}_{i}})}^{{{x}_{i}}}}r_{i}^{{{N }_{i}}}\bmod N_{i}^{2}, \\

{{X}_{i}} ={{x}_{i}}\cdot G, \\

{{x}_{i}} \in {{\mathbb{Z}}_{\tilde{q}}}

{{X}_{i}} ={{x}_{i}}\cdot G, \\

{{x}_{i}} \in {{\mathbb{Z}}_{\tilde{q}}}

\end{array} \right.} \right\}$$

Передача фрагмента открытого ключа $X_i$, зашифрованного текста $c_{key,i}$ и трёх zk-доказательств.

**Шаг 5:** Когда каждый пользователь $i$ получает фрагменты открытого ключа других пользователей ${{X}_{j}},j\ne i$ и доказательство zk, проверьте три доказательства zk. Кроме того, каждый пользователь проверяет согласованность интерполяции Лагранжа следующим образом:

$$PK=\lambda _{i,j}\cdot X_i +\lambda _{j,i}\cdot X_j,$$

Среди них $\lambda_{i,j}$ и $\lambda_{j,i}$ — соответствующие коэффициенты интерполяции Лагранжа.

После завершения выполнения протокола децентрализованной генерации ключей каждый пользователь $i$ получит фрагмент закрытого ключа $x_i$, фрагмент открытого ключа $X_i$, совместный открытый ключ $PK$ и $n-1$ зашифрованный текст $ c_{key_j}, j \neq i$.

## Протокол 2: децентрализованное обновление ключей

**Шаг 1:** Каждый пользователь $i,i=1,...,n$ выбирает случайное число $a_i'\in [0,\tilde{q}-1]$ и строит **полином Лагранжа * *:

$$p_i'(x)=x\cdot a_i'.$$

Обратите внимание, что постоянный член равен 0. Сохраните ${{p}_{i}}'(i)$ и тайно отправьте ${{p}_{i}}'(j)$ каждому пользователю $j$. Затем вычислите **кортеж Фельдмана**.

$$A_i':=a_i'\cdot G$$

Трансляция $A_i'$.

**Шаг 2:** Каждый пользователь $i$ получает $p_j'(i)$ и $\{A_j'\},j=1,...,n$ от других пользователей и проверяет элемент **Feldman. Согласованность группы**:

$$p_j'(i)\cdot G=i\cdot A_j'.$$

Рассчитайте новый фрагмент закрытого ключа и новый фрагмент открытого ключа следующим образом:

$$\begin{выровнено}

& x_i':=x_i+a_j', \\

& X_i':=x_i'\cdot G. \\

\end{aligned}$$

Затем zk-Шнорр доказывает, что знает $x_i'$.

Зашифруйте $x_i'$, используя открытый ключ Paillier ${{N}_{i}}$

$$c_{key,i}':=\mathsf{Enc}_{{{N}_{i}}}(x_i')$$

доказательство диапазона zk:

$$zk\left\{ {x_i',r_i'\left| \begin{array}{l}

c_{key,i}' = {(1 + {N_i})^{x_i'}}{(r_i')^{{N_i}}}\bmod N_i^2\\

X_i' = x_i' \cdot G\\

c_{key,i}' = {(1 + {N_i})^{x_i'}}{(r_i')^{{N_i}}}\bmod N_i^2\\

X_i' = x_i' \cdot G\\

x_i' \in {\mathbb{Z}_{\tilde q}}

\end{array} \right.} \right\}$$

Передача нового фрагмента открытого ключа $X_i'$, зашифрованного текста $c_{key,i}'$ и двух zk-доказательств.

**Шаг 3:** Каждый пользователь $i$ получает фрагменты открытого ключа других пользователей $X_j',j\ne i$ и два zk-доказательства и проверяет достоверность двух zk-доказательств. Дополнительно каждый пользователь может проверить корректность интерполяции Лагранжа:

$$PK=\lambda _{i,j}\cdot X_i' +\lambda _{j,i}\cdot X_j',$$

Среди них ${{\lambda }_{i,j}}$ и ${{\lambda }_{j,i}}$ — соответствующие коэффициенты интерполяции Лагранжа.

После завершения протокола обновления децентрализованного ключа каждый пользователь $i$ получает новый фрагмент закрытого ключа $x_i'$, новый фрагмент открытого ключа $X_i'$ и $n -1$ новый зашифрованный текст $c_{key_j}',j \neq я$.

## Соглашение 3: Предварительно подписанное соглашение

**Шаг 1:** Пользователь $i$ выбирает случайное число ${{k}_{i}}\in [0,\tilde{q}-1]$, рассчитываемое следующим образом:

$${{R}_{i}}:={{k}_{i}}\cdot G.$$

zk-Шнорр доказывает, что знает случайное число ${{k}_{i}}$:

$$proo{{f}_{i}}:=zk\left\{ {{k}_{i}}\left| {{R}_{i}}={{k}_{i}} \cdot G \right \right\}.$$

Для ${{R}_{i}}$ и $proo{{f}_{i}}$ рассчитайте обязательство и откройте обязательство

$$\left[ KG{{C}_{i}},KG{{D}_{i}} \right]:=\mathsf{Com}({{R}_{i}},proo{{ f}_{i}}).$$

Отправьте обязательство $KG{{C}_{i}}$ пользователю $j$.

**Шаг 2:** Получив обязательство $KG{{C}_{i}}$, пользователь $j$ выбирает случайное число ${{k}_{j}}\in [0,\tilde { q}-1]$, вычислить

$${{R}_{j}}:={{k}_{j}}\cdot G$$

zk-Шнорр доказывает, что знает случайные числа

$$proo{{f}_{j}}:=zk\left\{ {{k}_{j}}\left| {{R}_{j}}={{k}_{j}} \cdot G \right \right\}.$$

Затем отправьте $({{R}_{j}},proo{{f}_{j}})$ пользователю $i$.

**Шаг 3:** После получения $({{R}_{j}},proo{{f}_{j}})$ пользователь $i$ проверяет согласованность обязательства. Если противоречиво, отклонить; в противном случае фиксация $KG{{D}_{i}}$ будет открыта и отправлена ​​пользователю $j$.

**Шаг 4:** После получения $({{R}_{i}},proo{{f}_{i}})$ пользователь $j$ проверяет согласованность обещания. Если противоречиво, отбраковывайте, в противном случае рассчитывайте следующим образом:

$$\begin{выровнено}

R&:={{k}_{j}}\cdot {{R}_{i}}, \\

$$\begin{выровнено}

R&:={{k}_{j}}\cdot {{R}_{i}}, \\

r&:={{R}_{[x]}}\bmod \tilde{q},

\end{aligned}$$

где ${{R}_{[x]}}$ представляет собой координату $x$ точки $R$.

Выберите случайное сообщение ${{m}_{0}}\in [0,\tilde{q}-1]$ и случайное число $\rho \in [0, {{\tilde{q}}^{ 2}}-1]$, вычислить

$${{c}_{0}}:=\mathsf{Enc}_{{{N}_{i}}}(k_{j}^{-1}\cdot {{m}_{0} }\bmod \tilde{q}+\rho \cdot \tilde{q}).$$

Затем рассчитайте следующим образом

$$\begin{выровнено}

& {{c}_{1}}:=\left( ({{\lambda }_{i,j}}\odot {{c}_{key,i}})\oplus \mathsf{Enc}_ {{{N}_{i}}}({{\lambda }_{j,i}}{{x}_{j}}) \right)\odot (k_{j}^{-1}r ), \\

& {{c}_{2}}:={{c}_{0}}\oplus {{c}_{1}} \\.

\end{aligned}$$

Наконец, ${{c}_{2}}$ отправляется пользователю $i$ и сохраняется $({{m}_{0}},r)$.

**Шаг 5:** После получения ${{c}_{2}}$ пользователь $i$ использует свой закрытый ключ Paillier для расшифровки следующим образом.

$${{s}_{0}}:=\mathsf{Dec}_{{{p}_{i}},{{q}_{i}}}({{c}_{2}} ).$$

Затем рассчитайте следующим образом

$$\begin{выровнено}

& {{s}_{1}}:=k_{i}^{-1}\cdot {{s}_{0}}\bmod \tilde{q}, \\

& R':={{k}_{i}}\cdot {{R}_{j}},\\

& r':=R_{[x]}'\bmod \tilde{q}.

\end{aligned}$$

Сохраните ${{s}_{1}}$ и $r'$.

*Анализ 1:*

потому что

$${{k}_{j}}\cdot {{R}_{i}}={{k}_{i}}{{k}_{j}}\cdot G={{k}_ {i}}\cdot {{R}_{j}}$$

Следовательно, $R=R'$, следовательно, $r=r'$.

С другой стороны, выражение для ${{c}_{1}}$ имеет вид:

$$\begin{выровнено}

{{c}_{1}} & =\left( ({{\lambda }_{i,j}}\odot {{c}_{key,i}})\oplus \mathsf{Enc}_{ {{N}_{i}}}({{\lambda }_{j,i}}{{x}_{j}}) \right)\odot (k_{j}^{-1}r) \\

{{c}_{1}} & =\left( ({{\lambda }_{i,j}}\odot {{c}_{key,i}})\oplus \mathsf{Enc}_{ {{N}_{i}}}({{\lambda }_{j,i}}{{x}_{j}}) \right)\odot (k_{j}^{-1}r) \\

& =\left( \mathsf{Enc}_{{{N}_{i}}}({{\lambda }_{i,j}}{{x}_{i}})\oplus \mathsf{ Enc}_{{{N}_{i}}}({{\lambda }_{j,i}}{{x}_{j}}) \right)\odot (k_{j}^{- 1}р) \\

& =\mathsf{Enc}_{{{N}_{i}}}({{\lambda }_{i,j}}{{x}_{i}}+{{\lambda }_{j ,i}}{{x}_{j}})\odot (k_{j}^{-1}r) \\

& =\mathsf{Enc}_{{{N}_{i}}}(x)\odot (k_{j}^{-1}r) \\

& =\mathsf{Enc}_{{{N}_{i}}}(k_{j}^{-1}rx \\.

\end{aligned}$$

Выражение ${{c}_{2}}$:

$$\begin{выровнено}

{{c}_{2}} & ={{c}_{0}}\oplus {{c}_{1}} \\

& =\mathsf{Enc}_{{{N}_{i}}}(k_{j}^{-1}{{m}_{0}}\bmod \tilde{q}+\rho \tilde {q})\oplus \mathsf{Enc}_{{{N}_{i}}}(k_{j}^{-1}rx) \\

& =\mathsf{Enc}_{{{N}_{i}}}(k_{j}^{-1}{{m}_{0}}\bmod \tilde{q}+\rho \tilde {q}+k_{j}^{-1}rx).

\end{aligned}$$

Следовательно, выражение для ${{s}_{0}}$ имеет вид:

$${{s}_{0}}=k_{j}^{-1}{{m}_{0}}\bmod \tilde{q}+\rho \tilde{q}+k_{j} ^{-1}rx.$$

Выражение ${{s}_{1}}$:

$$\begin{выровнено}

{{s}_{1}} & =k_{i}^{-1}{{s}_{0}}\bmod \tilde{q} \\

& =k_{i}^{-1}k_{j}^{-1}{{m}_{0}}\bmod \tilde{q}+k_{i}^{-1}k_{j} ^{-1}rx\bmod \tilde{q} \\

& ={{k}^{-1}}{{m}_{0}}+{{k}^{-1}}rx\bmod \tilde{q} \\.

\end{aligned}$$

*Анализ 2:* Если необходимо достичь активного и безопасного порогового подписания, участники должны обновлять свои фрагменты закрытого ключа после каждой подписи. Протокол обновления ключа требует двух раундов взаимодействия, а протокол предварительного подписания — 4 раунда. Для повышения эффективности эти два протокола могут быть интегрированы. В частности, интерактивные данные протокола предварительного подписания и протокола обновления децентрализованного ключа могут передаваться одновременно. Этот подход исключает два отдельных раунда взаимодействия для протокола децентрализованного обновления ключей и упрощает такие процессы, как аутентификация пользователей, повышая эффективность.

## Протокол 4: Онлайн-подпись

**Шаг 1:** Для сообщения $msg$ пользователь $j$ вычисляет

## Протокол 4: Онлайн-подпись

**Шаг 1:** Для сообщения $msg$ пользователь $j$ вычисляет

$$\tilde{m}:=(\mathsf{Hash}(msg)-{{m}_{0}})\bmod \tilde{q}.$$

затем вычислить

$${{c}_{3}}:=\mathsf{Enc}_{{{N}_{i}}}(k_{j}^{-1}\tilde{m}\bmod \tilde{ д}).$$

Отправьте ${{c}_{3}}$ пользователю $i$.

**Шаг 2:** Получив ${{c}_{3}}$, пользователь $i$ использует свой закрытый ключ для расшифровки.

$${{s}_{2}}:=\mathsf{Dec}_{{{p}_{i}},{{q}_{i}}}({{c}_{3}} ).$$

Затем рассчитайте его следующим образом:

$$\begin{выровнено}

& {{s}_{3}}:=(k_{i}^{-1}{{s}_{2}})\bmod \tilde{q}, \\

& {{s}_{4}}:=({{s}_{1}}+{{s}_{3}})\bmod \tilde{q} \\.

\end{aligned}$$

Пусть $s=\min \{{{s}_{4}},\tilde{q}-{{s}_{4}}\}$. Для сообщения $msg$, если $(r, s)$ — действительная подпись, принять ее, в противном случае — отклонить;

*Анализ 1:* Выражения ${{s}_{2}}$ и ${{s}_{3}}$ соответственно

$$\begin{выровнено}

& {{s}_{2}}=k_{j}^{-1}\tilde{m}\bmod \tilde{q}, \\

& {{s}_{3}}=k_{i}^{-1}k_{j}^{-1}\tilde{m}\bmod \tilde{q}={{k}^{-1 }}\tilde{m}\bmod \tilde{q} \\.

\end{aligned}$$

Выражение ${{s}_{4}}$ равно

$$\begin{выровнено}

{{s}_{4}} & =({{s}_{1}}+{{s}_{3}})\bmod \tilde{q} \\

& ={{k}^{-1}}{{m}_{0}}+{{k}^{-1}}rx+{{k}^{-1}}\tilde{m}\bmod \tilde{q} \\

& ={{k}^{-1}}(\tilde{m}+{{m}_{0}})+{{k}^{-1}}rx \\

& ={{k}^{-1}}(\mathsf{Hash}(msg)+rx) .\\

\end{aligned}$$

Следовательно, $(r, s)$ является допустимой подписью для сообщения $msg$.

*Анализ 2:*

\end{aligned}$$

Следовательно, $(r, s)$ является допустимой подписью для сообщения $msg$.

*Анализ 2:*

(1) Симметрия эллиптической кривой придает пластичность сигнатуре ECDSA. Если $(r, s)$ — действительная подпись, то $(r, \tilde{q}-s)$ также действительна. Таким образом, протокол пороговой подписи 2-n страдает гибкостью, т. е. как $(r, s)$, так и $(r, \tilde{q}-s)$ являются действительными подписями. Чтобы предотвратить эту проблему, используйте $s = \min\{s, \tilde{q}-s\}$ для стандартизации значения $s$ и устранения пластичности (2) Чтобы предотвратить атаки BitForge, если подпись; не удалось, то внедрите протокол децентрализованного обновления ключей.

**Рекомендации**

1. Линделл Ю. Быстрое безопасное двустороннее подписание ECDSA[C] // Достижения в криптологии – CRYPTO 2017: 37-я ежегодная международная конференция по криптологии, Санта-Барбара, Калифорния, США, 20–24 августа 2017 г., Материалы, Часть II 37. Springer International Publishing, 2017: 613-644.

2. Канетти Р., Дженнаро Р., Голдфедер С. и др. Неинтерактивный, упреждающий, пороговый ECDSA UC с идентифицируемыми прерываниями [C] // Материалы конференции ACM SIGSAC 2020 года по компьютерной и коммуникационной безопасности. 2020: 1769-1787.

3. Макрияннис Н., Йомтов О.: Практические атаки с извлечением ключей в ведущих кошельках MPC [J]. Архив криптологии ePrint, 2023.

О СИНОХОПЕ

SINOHOPE Technology Holdings Co., Ltd. (именуемая «SINOHOPE», биржевой код: 1611.HK) специализируется на хранении цифровых активов и предоставляет различные решения по хранению, которые помогают каждому предприятию использовать цифровые активы безопасно и удобно. Основной продукт компании, самостоятельная платформа MPC SINOHOPE, использует технологию MPC-CMP для поддержки распределенного управления пользователями сегментами закрытых ключей и совместных подписей, устраняя точечные риски, связанные с закрытыми ключами, и эффективно повышая прозрачность и простоту использования.

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

Сайт компании: www.sinohope.com.

Консультация инвестора: [email protected]

Для запросов СМИ: [email protected]