Develop with pleasure!

福岡でCloudとかBlockchainとか。

3ラウンドのECDSA閾値署名プロトコルDKLS23

ECDSA Cryptography MPC

ECDSAベースの閾値署名というと、GG18/20あたりが有名↓

techmedia-think.hatenablog.com

これらのプロトコルは加法準同型性のある暗号化方式であるPaillier暗号に依存しており、署名の生成に6ラウンドの通信を必要とする。

その後提案されたDKLS23という署名スキーム↓は、準同型暗号の代わりに紛失通信を活用した閾値署名スキームで、署名生成が3ラウンドで行えるというメリットがある。

eprint.iacr.org

DKLS23

まず最初に分散鍵生成とゼロシェアのセットアップを行う。

鍵生成プロトコル

GG18/20など従来の閾値署名プロトコルの分散鍵生成（DKG）は、PedersenのVSSなどが採用されていたけど、DKLS23ではRelaxed DLog Keygenという鍵生成プロトコルを採用している。

参加者の数をn、閾値をtとした場合、鍵生成の流れは↓

  1. 各参加者 {P_i}はそれぞれランダムな多項式 {p_i(x)}を選択する。また多項式を評価してベースポイントを乗算した値を {P_(x) = p(x)G}とする。
  2. 各参加者 {P_i}は、 {k \in \lbrack 0, t - 1 \rbrack}について {P_i(k)}を計算し、
  3. 2に対するコミットメント {commitment_i = H(P_i(0) || ... || P_i(t-1) || salt)}を計算し、他の参加者に共有する。※ ここでは閾値の数分のコミットメントだけを計算し、全員に共有する。
  4. 次に各参加者は参加者全員分（n人分）の多項式の評価値 {p_i(j)}（つまりシェア）を計算し（2は楕円曲線上の点だけど、こちらはスカラー値のまま）、そのコミットメント {H(p_i(j) || salt_{i, j})}を計算し、そのコミットメントを各参加者 {P_j}に個別に送信する。
  5. 参加者全員から、3と4のコミットメントを受け取ったら、コミットした値をデコミットする。
    • 2のコミットメントについては、それぞれ {P_i(0) || ... || P_i(t-1) || salt)}をブロードキャストして開示する。
    • 4のコミットメントについては、それぞれ {p_i(j), salt_{i, j}}を個別に開示する。
  6. 参加者iからデコミットされたデータを受け取った各参加者jは以下の検証を行う。
    • ブロードキャストされた楕円曲線上の点を使ってラグランジュ補間を行い {P_i(j)}を計算し、
    • 個別開示された {p_i(j) \cdot G}が先に受け取ったコミットメントと一致するか検証し、かつラグランジュ補間で導出した点と一致するか検証する。
  7. 検証をパスしたら、全参加者がブロードキャストしたt個の点の先頭の点、つまり {P_i(0)}を合算して、公開鍵とする。つまり、各参加者が生成した多項式の定数項の点を合算した点が公開鍵。

これで各参加者がそれぞれ秘密鍵のシェア {p(i)}を持つ状態になる。

PedersenのVSSと比較すると、ラウンド数が少なく、コミットメント作成時の楕円曲線演算の数が少なく、自身が秘密鍵を知っていることの証明を必要としないなど、効率的。ただ、論文では、

We stress that our relaxed key generation functionality is sufficient for use with the signing protocol proposed in this work, but it cannot necessarily be used with other threshold signing protocols that use discrete-log keypairs.

とあり、DKLS23で使用する分には十分だけど、他の閾値署名プロトコルで必ずしも使えるとは限らないと。

Relaxedとあるのは、実際に署名を作成する際のラウンドで、以下のゼロシェアを使って秘密鍵のシェアを再ランダム化するので、秘密鍵の知識の証明が求められるのはそこ（署名の第3ラウンドの一貫性チェック）まで遅延されることが由来。

ゼロシェアのセットアップ

二者間で共有される秘密のランダム値であるペアワイズシードを生成する。

アリスとボブで生成する場合、

  1. 両者はそれぞれランダムなシードを選択する（アリスのシードを {seed_{ab}}、ボブのシードを {seed_{ba}}）とする。
  2. 両者は1のシードのコミットメント{commitment_a = H(seed_{ab} | nonce_a)}、 {commitment_b = H(seed_{ba} || nonce_b)}を計算し、自分が計算したコミットメントを相手に送る。
  3. コミットメントを交換したら、それぞれコミットしたシードを相手に開示する。
  4. 両者は自分のシードど相手のシードのXORを計算し共有シード {shared-seed_{a,b} = seed_{ab} \oplus seed_{ba}}を計算する

上記のペアワイズシードを署名の全参加者分、それぞれ協力してセットアップする。

ゼロシェアというのは、すべてのシェアを加算するとその結果がゼロになるシェアのことで、署名プロセスで各参加者が上記のペアワイズシードを元に導出する。たとえば3人でゼロシェアを生成する場合、参加者 {P_1, P_2, P_3}は、それぞれ

  • {P_1}： {shared-seed_{1, 2}}、 {shared-seed_{1, 3}}
  • {P_2}： {shared-seed_{1, 2}}、 {shared-seed_{2, 3}}
  • {P_3}： {shared-seed_{1, 3}}、 {shared-seed_{2, 3}}

を持っているので、以下のようにゼロシェアを計算できる。

  • {P_1}： {share_{1,2} = -H(shared-seed_{1, 2} || sigid)}、 {share_{1,3} = -H(shared-seed_{1, 3} || sigid)}
    そして{\zeta_1 = share_{1,2} + share_{1,3}}とする。
  • {P_2}： {share_{2,1} = H(shared-seed_{1, 2} || sigid)}、 {share_{2,3} = -H(shared-seed_{2, 3} || sigid)}
    そして{\zeta_2 = share_{2,1} + share_{2,3}}とする。
  • {P_3}： {share_{3, 1} = H(shared-seed_{1, 3} || sigid)}、 {share_{3,2} = H(shared-seed_{2, 3} || sigid)}
    そして{\zeta_3 = share_{3,1} + share_{3,2}}とする。

各シェアの値について、IDが小さい方の符号がマイナスとするルールを設けることで、上記シェアをすべて加算するとその合算値（ {\sum \zeta_i}）がゼロになることが保証される。そして一度セットアップしておけば、署名時にsigidによって、何回でも決定論的に異なるゼロシェアを導出できる。

署名プロトコル

前提として、2P-ECDSAやGG18/20ではPaillier暗号を使って乗法シェアを加法シェアに変換していた（MtA）が、DKLSの署名プロセスではPaillier暗号に代わってVOLEを利用する↓

techmedia-think.hatenablog.com

公開鍵をP = xG（xは秘密鍵）、署名対象のメッセージをm、ハッシュ関数をH、楕円曲線のベースポイントをGとした場合、通常、ECDSA署名は以下のように生成される。

  1. ランダムなnonce値kを選択し、
  2. 公開nonce R = kGを計算し、r = R.x（点RのX座標）とする。
  3. {\displaystyle s = \frac{H(m) + r \cdot x}{k}}を計算し、
  4. (r, s)がECDSA署名

DKLS23では、上記のECDSAのsを求める式を以下のように分解する。

  • {w = (H(m) + r \cdot x) \cdot \phi}、
  • {u = k \cdot \phi}とし、
  • sは、 {\displaystyle s = \frac{w}{u}}

{\phi}はランダムなマスク値で、最終的なsの計算結果自体は変わらない。

DKLS23の署名プロトコルは、以下の3つのラウンドで構成される。

第1ラウンド

第1ラウンドでは、各参加者は、署名に使用するnonceのシェアにコミットする。

各参加者iは、それぞれ

  1. ランダムな値 {k_i, \phi_i}を選択し、
  2. 公開nonce {R_i = k_i G}を計算し、
  3. 他の参加者（j）へのコミットメント {commitment_{i, j} = H(R_i || salt_{i, j})}を計算する
  4. 他の参加者へ3のコミットメントと送信し、二者間のVOLEをセットアップする
  5. ゼロシェア {\zeta_i}を計算する

{\phi_i}をサンプリングしたりゼロシェアを計算してるけど、この値が実際に使われるのは次のラウンド。

第2ラウンド

第2ラウンドは、秘密の値のMtA変換とその正しさの証明準備をするラウンド。また、第1ラウンドでコミットした各公開nonceのシェアをデコミットする。

参加者iは、

  1. 保持する秘密鍵のシェア {p(i)}とゼロシェア {\zeta_i}を使って秘密鍵のシェアを再ランダム化する。具体的には、 {sk_i = p(i) \cdot ラグランジュ係数 + \zeta_i}を計算する。
  2. 2つの要素のベクトル {(k_i, sk_i)}を入力として、他の参加者jとVOLEを実行する。その際、参加者jはランダムな値 {\chi_{j, i}}を選択し、両者は {c^{u}_{i, j} + d^{u}_{j, i} = k_i \cdot \chi_{j, i}}および {c^{v}_{i, j} + d^{v}_{j, i} = sk_i \cdot \chi_{j, i}}を満たす加法シェアを得る。VOLEを利用することで、 {(k_i, sk_i)}に対して同じ値が乗算される。
    • 参加者iは、 {(c^{u}_{i, j}, c^{v}_{i, j})}を保持
    • 参加者jは、 {(d^{u}_{j, i}, d^{v}_{j, i})}を保持
  3. VOLEの結果、以下を計算する。この時、 {\chi_{i, j}}は、2のVOLEをj基点で行った際にiがランダムに選択する値。
    • {\Gamma^{u}_{i, j} = c^{u}_{i, j} \cdot G}
    • {\Gamma^{v}_{i, j} = c^{v}_{i, j} \cdot G}
    • {pk_i = sk_i \cdot G}
    • {\psi_{i, j} = \phi_i - \chi_{i, j}}
  4. 最後に、第1ラウンドでコミットした公開nonce {R_i}と、3で計算した値を参加者jに送る。
第3ラウンド

最後のラウンドでは、第2ラウンドで受け取ったデータの検証を行い、最終的な署名を組み立てる。

参加者iは、

  1. jから受け取ったデータについて、以下の一貫性チェックをすることで、VOLEでjの {(k_j, sk_j)}に対して自分が選択したランダム値 {\chi_{i, j}}との積の加法シェアの正しさを検証する。
    • {\chi_{i,j} \cdot R_j - \Gamma^{u}_{j, i} = d^{u}_{i, j} \cdot G}
    • {\chi_{i,j} \cdot pk_j - \Gamma^{v}_{j, i} = d^{v}_{i, j} \cdot G}
  2. {\sum pk_i}を計算し、全体の公開鍵と合致するかチェックし、ゼロシェアで再ランダム化されていることを検証する。
  3. ↑のチェックをパスしたら、署名参加者から受け取った公開nonceを合算して署名に使用する公開nonce {R = \sum R_i}を導出し、r = R.xとする。
  4. 続いて、以下の値を計算する。
    • {u_i = k_i \cdot (\phi_i + \sum \psi_{j, i}) + \sum (c^{u}_{i, j} + d^{u}_{i, j})}
    • {v_i = sk_i \cdot (\phi_i + \sum \psi_{j, i}) + \sum (c^{v}_{i, j} + d^{v}_{i, j})}
    • {w_i = H(m) \cdot \phi_i + r \cdot v_i}
  5. 他の参加者に署名の断片 {w_i, u_i}を送信する。
  6. 参加者分の5が集まったら、 {\displaystyle \frac{\sum w_j}{\sum u_j}}を計算する。
    • {\sum u_j}はu、つまり {u = k \cdot \phi}の計算にあたる。 {u_i}の計算は、参加者は自分の {\phi_i}は知っているけど、他の参加者の値は知らないので、それを {\psi_{i, j} }を使って間接的に計算してるのが {k_i \cdot (\phi_i + \sum \psi_{j, i}) }の部分。ただ {\psi_{i, j} }を使うと余計な {-\chi_{i, j}}が含まれてしまうので、それを相殺するのが {\sum (c^{u}_{i, j} + d^{u}_{i, j})}の役割。その結果 {u_i}は {k_i \cdot \phi}の結果になる。
    • {\sum w_j}はw、つまり {w = (H(m) + r \cdot x) \cdot \phi}の計算にあたる。 {w_i}の計算は、 {H(m) \cdot \phi_i }の部分はまぁ自明で、 {v_i}の式は上述の {u_i}のロジックと同じで、 {v_i = sk_i \cdot \phi}を計算している。
  7. (r, s)を検証し、正しければ署名データの完成

以上がDKLS23の署名プロトコル。