Develop with pleasure!

福岡でCloudとかBlockchainとか。

２ラウンドで安全なマルチシグを生成する署名スキームMuSig2

Cryptography Schnorr

MuSigはもともとSchnorr署名の鍵の集約特性を活かして多重署名（マルチシグ）を単一のSchnorr署名で行う署名スキームで、Rogue-key攻撃に対して堅牢な署名スキーム↓

techmedia-think.hatenablog.com

ただ、署名の生成に以下の３ラウンドの通信が必要になる。

  1. nonce値のコミットメントの交換
  2. nonceの交換
  3. 部分署名の交換

そして、今回新しくMuSig2が公開された↓

https://eprint.iacr.org/2020/1261

MuSig2の署名方式

MuSig2では署名生成時の通信ラウンドも３→２に減らすことができる。↑のMuSigの3ラウンドの通信の内、１のnonceのコミットメントの交換プロセスを省略するみたい。省略してどう安全性を担保するのか？具体的な署名方式を見てみよう。

表記

  • {x_1, x_2, ..., x_n}を署名プロセスに参加する各ユーザーの秘密鍵とし、対応する公開鍵を {X_1 = x_1G, X_2 = x_2G, ..., X_n = x_nG}とする。
  • 集約する公開鍵のリストを {L = (X_1, ..., X_n)}とする。
  • 署名対象のメッセージをmとする。

署名の生成

各署名者は以下の手順で署名を生成する。

  1. n人の署名者（署名者のインデックスをiとする）はv個のランダムな値（インデックスをjとする） {r_{i, j}}を生成する。
  2. 1で生成した値についてPublic nonce {R_{i, j} = r_{i, j}G}を計算する。
  3. 署名者iは、２で導出したPublic nonceのリスト {R_{i, 1}, ..., R_{i, v}}を他の署名者にブロードキャストする。
  4. 署名者iは、各署名者の公開鍵から {a_i = H_{agg}(L, X_i)}を計算する。
  5. 署名者は４で計算した値を使って、集約公開鍵 {\displaystyle \tilde{X} = \sum_{i=1}^n a_i X_i}を計算する。
  6. 他の全参加者からPublic nonce のリストを受信したら、全参加者の同じインデックスjのPublic nonce {\displaystyle R_j = \sum_{i=1}^n R_{i, j}}を集約する。
  7. 続いて、v個の係数のベクトル {(b_1, ..., b_v)}を計算する。 {b_1 = 1}で、それ以降のbの値は {\displaystyle b_j = H(j, \tilde{X}, (R_1, ..., R_v), m)}として計算する。つまりこのbは決定論的に生成される。
  8. ここでPublic nonceを集約して署名に使用する集約nonce {\displaystyle R = \sum_{j=1}^v b_j R_j}を計算する。
  9. さらに署名に使用するチャレンジ {\displaystyle c = H_{sig}(\tilde{X}, R, m)}を計算する。
  10. そして自身の部分署名 {\displaystyle s_i = c a_i x_i + \sum_{j=1}^v r_{i, j} b_j \mod p}を計算し、他の署名者にブロードキャストする。
  11. すべての参加者の署名値を受け取ると、 {\displaystyle s = \sum_{i=1}^n s_i \mod p}を計算する。
  12. 最終的な署名値は（R, s）

署名の検証

署名者は以下を実行して署名が正しいか検証する。

  1. 各署名者の公開鍵から、 {a_i = H_{agg}(L, X_i)}を計算する。
  2. 1から集約公開鍵 {\displaystyle \tilde{X} = \sum_{i=1}^n a_i X_i}を計算する。
  3. 集約公開鍵と署名対象のメッセージおよび、署名データのRを使って、署名に使用するチャレンジ {c = H_{sig}(\tilde{X}, R, m)}を計算する。
  4. 最後に {\displaystyle sG = R + c\tilde{X} = R + \sum_{i=1}^n a_icX_i}が成立するか検証する。成立していれば署名は有効。

集約公開鍵の算出と、チャレンジの作成方法の部分が通常とは異なるが、最後の検証式は通常のSchnorr署名の検証式と同じ。

MuSigとの違い

集約公開鍵 {\tilde{X}}の計算方法は、MuSigと同じでこれがRogue-key攻撃への耐性となるポイント。

MuSigと違うのは署名に使用するnonceの取り扱い。MuSigでは各参加者がPublic nonce {R_i}を交換する前に、必ず {R_i}へのコミットメントを交換し、全員分のコミットメントが揃った上で {R_i}を交換する。

MuSigでnonceのコミットメントの交換が必要な理由

コミットメントの交換ラウンドを省略したり、事前にコミットメントおよびnonceの交換をした場合にどんな問題が起きるかは、Tim Ruffingの発表が分かりやすい。

問題になるのは、複数の署名セッションを並列して実行するケース。

攻撃にはWagnerのアルゴリズムを使用する。このアルゴリズムを利用すると、暗号学的ハッシュ関数Hを使用した場合

  • {H(m_0) = H(m_1)}となるような {m_0, m_1}を発見するのは困難だが、
  • {H(m_0) = H(m_1) + H(m_2 + ... + H(m_n))}となるような {m_0, m_1, ..., m_n}を発見するのは簡単

になる（メッセージの数が増える程、必要な計算量は減る）。

被害者の鍵ペアを {X_1 = x_1G}、攻撃者の鍵ペアを {X_2 = x_2G}、両者の集約公開鍵を {X = X_1 + X_2 = (x_1 + x_2)G}とする。

  1. 攻撃者は被害者との間に、メッセージmの異なる署名セッションを複数、並列実行する。
  2. 被害者がセッションの数分、Public Nonce = {R_1, R_2, ..., R_n}を送信する（ {R = \sum_{i=1}^n R_i}とする）。
  3. 攻撃者は、ワグナーのアルゴリズムを使って {H(P, R, m) = H(P, R_1 + R'_1, m_1) + ... + H(P, R_n + R'_n, m_n)}となるPublic nonce {R'_1, R'_2, ..., R'_n}を見つける。右辺が各署名セッションで使われるハッシュ値。
  4. 攻撃者は３で見つけたPublic nonceのリストを被害者に送る。
  5. 被害者はこれらの値を使って部分的な署名 {s_1, ..., s_n}を計算する。
  6. 被害者の部分署名をすべて加算し、攻撃者が自身の部分的な署名を加えると、Public nonce Rとメッセージmについて有効な両者のSchnorr署名が完成する。

ここで、被害者は一度もメッセージmに対して部分署名を作ってはいない。にも関わらずmに対して有効な署名が作れてしまう。つまり、同じ鍵に対して複数の署名セッセションを実行することで（事前にnonceにコミットしていない場合）、偽のメッセージに署名させることができてしまう。

↑が可能なのは、攻撃者が被害者からPublic nonceを受信した後で自身のPublic nonceを細工可能であるからで、この攻撃を回避するためには、Public nonceを交換する前にそのコミットメントを交換する必要がある。これがMuSigでコミットメントの交換ラウンドが必要になっている理由。

尚、コミットメント自体は署名時ではなくても、事前に共有しておくことが可能で、MuSigを実装したBlockstreamが開発しているlibsecp-zkpでは、コミットメントの事前シェアが可能になっている。

MuSig2でコミットメントの交換を不要にしたポイント

MuSig2では、コミットメントの事前交換をせずに↑のWagnerのアルゴリズムを使った攻撃にどう対処しているのか？

↑の攻撃は、同時署名セッションのそれぞれの最初のラウンドで集約Public nonceを制御することで、署名ハッシュを制御する機能に依存している。

MuSig2では、各署名者が１回の署名セッションで生成するnonceが１つではなくv個になっている。そして部分署名を生成する際もnonce {r_i}単体が単純な加算要素となる訳ではなく、

  • 両者のPublic nonceから係数ベクトル値bを決定論的に生成し、
  • 生成した各係数値をそれぞれのPublic nonceに乗算して集約Public nonceを生成している

この結果、↑のような集約Public nonceの制御が困難になるというのが、コミットメントラウンドを排除できた仕組みみたい。

実際にnonceの生成個数vの値については、ランダムオラクルモデル（ROM）においてv ≧ 4が推奨され、さらにROM + AGM（algebraic group model）の構成でv ≧ 2とされているので、そこまで大きい数値ではない。ただ、個数の根拠となってるセキュリティ証明あたりはまだよく理解できてない。

MuSig2のオーバーヘッド

MuSigと比べた場合のMuSig2のオーバーヘッドは、ブロードキャストするPublic nonceの値がv個に増えるのと、その個数分の操作の計算量。ただ↑のようにv値は小さいので、通信ラウンド１回分に比べたら小さなオーバーヘッドと言えそう。

決定性nonceの生成はNG

単体のSchnorr署名では問題ないが、MuSigやMuSig2などのSchnorrの多重署名スキームでは、決定性nonceの利用は攻撃による秘密鍵の漏洩に繋がるので、MuSig2でもnonceの生成（↑で各署名者がrを生成してる部分）では、安全な乱数生成器が必要になる。

現状、Schnorrの多重署名スキームで安全な決定性nonceを生成するスキームは、こないだ発表されたMuSig-DN↓のみ。

techmedia-think.hatenablog.com

※ ただ、MuSig-DNの場合、高価なゼロ知識証明の生成を必要とする。