MuSig2

GBECの解説動画の資料です。
https://goblockchain.network/2021/02/musig2/

Transcript

1. MuSig2
2. 1 MuSig2
 MuSig：Rogue-Key攻撃に耐性のあるSchnorrのマルチシグスキーム
 https://goblockchain.network/2019/04/musig/
 
 
 MuSig2：MuSigの署名時の通信ラウンド3回→2回に 減らす新しいスキーム
 https://eprint.iacr.org/2020/1261.pdf 
 

3. 2 MuSigのポイント
 • 参加者の公開鍵セット：{P 1 , P 2 , P 3 , …, P n }
 • 各鍵ペア：P i = x i G
 • 暗号学的ハッシュ関数： H
 • メッセージダイジェスト： m
 
 【集約公開鍵の計算】
 1. 全参加者の公開鍵セットからL = H(P 1 || P 2 || ... || P n ) を計算
 2. 参加者の数分a i = H agg (L || P i )を計算
 3. 集約公開鍵P = a 1 P 1 + a 2 P 2 + … + a n P n を計算
 
 全参加者の公開鍵を単純に加算（＝P 1 +P 2 +...+P n ）せず、各公開鍵に
 対して異なるスカラー値を乗算しているため、Rogue-Key攻撃を試みても、
 被害者の公開鍵を削除できず
 （P 2 = P 2 ' - P 1 とした場合P 1 + P 2 = P 2 'とできない）
 攻撃は成功しない

4. 3 MuSigの署名プロセス
 1. 各署名者はランダムなnonce k i を選択する
 2. Public nonce R i = k i Gを計算する
 3. コミットメントt i = H com (R i )を計算し、他の全参加者に送信する
 4. 他の全参加者のコミットメントを受け取った後、R i を送信する
 5. 他の参加者から受信したPublic nonceとコミットメントが一致するか検証
 6. 一致した場合は署名に使用するR = R 1 + R 2 + … + R n を計算
 7. c = H sig (P || R || m)を計算
 8. 部分署名 s i = k i + ca i x i mod pを計算
 9. 部分署名を他の参加者に送信
 10. 全員の部分署名を受信したらs = s 1 + s 2 + … +s n を計算
 11. σ=(R, s)が署名データ
 3回の通信ラウンドが発生する

5. 4 コミットメントの事前送信が必要な理由
 • Wagnerのアルゴリズム（一般化された誕生日攻撃問題を解く）
 a. H(m 0 ) = H(m 1 )となるm 0 、m 1 を発見するのは難しいが、
 b. H(m 0 ) = H(m 1 ) + H(m 2 ) + … + H(m 100 ) を見つけるのは簡単
 
 • 署名セッションの同時実行ケースにおける攻撃
 攻撃者は同じメッセージｍについて複数の署名セッションを並列実行する
 a. 被害者はセッションの数分、Public nonce = R 1 , R 2 , …, R n を送信
 b. 攻撃者はWagnerのアルゴリズムにより
 H(P||R||m) = H(P|| R 1 + R’ 1 ||m 1 ) + … +H(P, R n + R’ n || m n )
 を満たすR’ 1 , …, R’ n を見つけ、それを被害者に送信
 c. 被害者は自身と攻撃者のPublic nonceからRを計算し部分署名を計算
 d. 攻撃者は被害者の部分署名を集約するとH(P || R || m)について
 （つまり偽のメッセージに対して）有効な署名を入手できる。
 ※被害者は一度もmについて有効な部分署名は作っていない
 攻撃者は被害者のPublic nonceを受信後にnonceを計算できるため

6. 5 MuSig2では通信を2ラウンドに削減
 • 集約公開鍵の計算方法はMuSigと同じ＝Rogue-Key攻撃への耐性
 • MuSig2ではPublic nonceの構成方法を変更しコミットメントの交換を不要に
 a. 参加者はv個のランダムなnonce k 1 , k 2 , …, k v を選択
 b. v個のPublic nonceを計算（R 1 = k 1 G, R 2 = k 2 G, …, R v = k v G）
 c. v個のPublic nonceを他の参加者に送信
 d. インデックス毎にPublic nonceを集約R j = R 1,j + R 2,j + … + R n,j
 e. v個の係数ベクトルを計算する。b 1 = 1で、それ以外は、
 b j = H(j || P || (R 1 , …, R v ) || m)
 f. 署名用のPublic nonce R = b 1 R 1 + b 2 R 2 + … + b v R v を計算
 ※ ↑の特性から、Wagnerのアルゴリズムを利用した
 　nonceの細工が不可能に
 vの値はROMにおいて≧4、ROM+AGMにおいて≧2
 全参加者のPublic nonceから 
 係数ベクトルを決定論的に計算 
 係数値を集約Public nonceに乗算