はじめに

ECDSAで2者間署名を行う方法です。
すでに、やっている人がいますので、そちらも参照してください。

効率的な二者間のECDSAプロトコル
 Bitcoinスクリプトを使わないマルチシグを書いてみた

以下の論文を参考にしています。

おさらい

使用する式のおさらいです。

EC(楕円曲線)

小文字はスカラー、大文字は楕円曲線の点とします。
$G$は基点で、$n$を位数とします。
点と点は加算する事ができます。

\begin{array}{ll}
& G & \text{: base point} \\
& n & \text{: order} \\
& O = nG & \text{: zero} \\
& P_a = x_aG \\
& P_b = x_bG \\
& P_a + P_b = (x_a + x_b)G \\
& x_cP_a = (x_c\cdot x_a)G
\end{array}

elliptic curve/secp256k1（楕円曲線）

楕円曲線DSA(ECDSA)

メッセージは$m$です。
$\text{Hash}(\cdot )$はハッシュ関数です。
署名値は、値の小さい方をとります。

\begin{align*}
{\bf Signing : } \\
& P = xG \qquad \text{: public key and private key} \\
& R = kG \qquad \text{: random point} \\
& R : (x_R,y_R) \quad \text{: x coordinate of random point } \\
& r = x_R \\
& e = \text{Hash}(m) \quad \text{: message hash } \\
& s = \frac{e+rx}{k}  \pmod n\\
& s = \min\{s,n-s \pmod n\} \\
& (s,r) \ \text{: signature } \\
\end{align*}

ECDSA（楕円曲線DSA）

Paillier暗号(Paillier cryptosystem)

実際は乱数$r$とか剰余が必要ですが、簡単に以下のようにあらわします。
暗号化、復号化と、準同型加法と乗法は以下のとおりです。

\begin{align*}
{\bf Encryption : } \\
& c = \mathcal{Enc}(m) \\
{\bf Decryption : } \\
& m = \mathcal{Dec}(c) \\
{\bf addition : } \\
& c_1 = \mathcal{Enc}(m_1) \\
& c_2 = \mathcal{Enc}(m_2) \\
& c_3 = c_1 \times c_2 \\
& m_1 + m_2 = \mathcal{Dec}(c_3) \\
{\bf multiplication : } \\
& c_1 = \mathcal{Enc}(m_1) \\
& c_4 = c_1^{m_2} \\
& m_1 \times m_2 = \mathcal{Dec}(c_4) \qquad \\
\end{align*}

Paillier暗号(Paillier cryptosystem)

Two-Party ECDSA

AliceとBobが2-of-2のマルチ署名を行います。

準備

Aliceの秘密鍵、公開鍵、乱数は以下とします。
$P_a=x_aG,R_a=k_aG$
Bobの秘密鍵、公開鍵、乱数は以下とします。
$P_b=x_bG,R_b=k_bG$
$P_a,R_a,P_b,R_b\ $は予め合意しているものとします。
Aliceは、以下を計算します。
$$P = x_aP_b\ $$
Bobは、以下を計算します。
$$P = x_bP_a\ $$
どちらも、同じ$P$となります。
$$P=x_ax_bG$$
お互いの秘密鍵を知らずとも2-of-2の公開鍵を作成することが出来ます。

また、AliceはPaillier暗号の公開鍵をBobに渡しているとします。
※：Bobは暗号化できますが、復号化はできません。

署名

Aliceは、$R=k_aR_b$を計算し、Bobは、$\ R=k_bR_a$を計算します。
どちらも、同じ値になります。$R=k_ak_bG$
$R:(r_x,r_y)$とし、$r=r_x$とします。

メッセージ$m$のハッシュを$m'=\text{Hash}(m)$とします。

Aliceは以下を計算し、$c_{key}$をBobへ送ります。

\begin{align*}
c_{key} = \mathcal{Enc}(x_a)\  \\
\end{align*}

Bobは乱数$\ \rho\ (\rho<n)\ $を生成して以下を計算し、$c_3$をAliceへ送ります。

\begin{align*}
c_1 &= \mathcal{Enc}((k_b)^{-1}\cdot m'+\rho n) \\
c_2 &= (c_{key})^{x_b\cdot r\cdot (k_b)^{-1}} \\
c_3 &= c_1 \times c_2 \\
\end{align*}

Aliceは、$c_3$を複合して、自身の$(k_1)^{-1}$の乗算が署名値となります。

\begin{align*}
s' &= \mathcal{Dec}(c_3) \\
s &= s'\cdot (k_a)^{-1} \pmod n\\
s &= s = \min\{s,n-s \pmod n\} \\
\end{align*}

解説

暗号なしで流れを見てみます。
途中に乱数を加算していますが、うまく消えています。
ちなみに、Paillier暗号のビット長は2048bitあれば足ります。

\begin{array}{rl}
{\bf Alice } \rightarrow {\bf Bob :} & \\
& x_1 \\
{\bf Bob } \rightarrow {\bf Alice :} & \\
& c_1 = \frac{m'}{k_b} + \rho n \\
& c_2 = \frac{rx_ax_b}{k_b} \\
& c_3 = \frac{m'+rx_ax_b}{k_b} + \rho n\  \\
{\bf Alice :} & \\
& s = \frac{m'+rx_ax_b}{k_ak_b} \\
\end{array}

プログラミング

コードを作成しました。
いままで作成したサンプルを組み合わせたものなので、興味のある方はgithubを参照下さい。

さいごに

Lightning Specification 1.1 Proposal Statesにも「2p-ecdsa」があったので、勉強してみましたが、すでに「Paillier暗号」を使わないアプローチが出てました・・・

勉強しなおしorz