CoSiプロトコルの安全性の証明の欠陥を応用した、2ラウンドのMuSigが安全でないことの証明

Table of Contents

はじめに

この記事ではCoSiプロトコルの安全性の証明の欠陥を応用した、2ラウンドのMuSigが安全でないことの証明[1]を紹介します。
まず、記号の定義を説明し、CoSiプロトコルの説明、CoSiプロトコルの安全性の証明の欠陥を述べ、それを応用してMuSig安全性の証明の欠陥を述べます。

記号の定義

素数位数 $q$ の群を $\mathbb{G}=\langle g \rangle$ とし、 $\mathcal{O}^{dlog}(\cdot)$ を最大 $n$ 回呼び出されうる離散対数オラクルとする。
攻撃者 $\mathcal{A}$ の $ADV^{dl}_G$ を
$Pr[y=g^x:y\xleftarrow{\char36 }\mathbb{G},x \xleftarrow{\char36 }\mathcal{A}(y)]$ とし、この値は $\mathcal{A}$ と $y$ によってランダムに定まる。
$\mathcal{A}(\tau,\epsilon)$ が離散対数問題を解くとは、最大 $\tau$ 時間で解けてかつ、 $ADV^{dl}_G\geq \epsilon$ となること。
また、上のような攻撃者が存在しない時、離散対数は $(\tau,\epsilon)$ -困難である。
DL仮定とは、離散対数問題を解くのが困難だとする仮定。
また、攻撃者 $\mathcal{A}$ の $ADV^{n-omdl}_\mathbb{G}$ を
$Pr[\bigwedge_{i=0}^{n}y_i=g^{x_i}:(y_0,...,y_n)\xleftarrow{\char36 }\mathbb{G^{n+1}},(x_0,...,x_n)\xleftarrow{\char36 }\mathcal{A}^{\mathcal{O}^{dlog}(\cdot)}(y_0,...,y_n)]$ とし、この値は $\mathcal{A}$ と $y_0,...,y_n$ によってランダムに定まる。
$\mathcal{A}(\tau,\epsilon)$ がn-one-more離散対数問題を解くとは、最大 $\tau$ 時間で解けてかつ、 $ADV^{n-omdl}_\mathbb{G}\geq \epsilon$ となること。
また、上のような攻撃者が存在しない時、n-one-more離散対数は $(\tau,\epsilon)$ -困難である。
OMDL仮定とは、one-more離散対数問題を解くのが困難だとする仮定。
要するに一つの離散対数問題を解くのも、n個の離散対数問題を解くのも同様に難しいという仮定である。

CoSiプロトコルの説明

CoSi プロトコルは非常に巨大であることがありうる分散化されたグループが独立したサーバーで動いている時に、効率的にシュノア署名を生成するためのアルゴリズムである。概要は [3] のドキュメントを参照せよ。

アナウンス->コミットメント->チャレンジ->レスポンスという4つのフェーズが存在する。これをツリー状に分岐したパスを用いて各パーティに届けることで効率的に署名が構成できるとされる。

署名者 $S_i$ に対して、秘密鍵は $sk_i$ 、公開鍵は $pk=(y_i,\pi_i)$ で定義される。
署名者 $S_i$ がリーダーならば、 $(t_i,PK_i)$ を親に送る代わりに、 $(\bar t,PK)=(t_i,PK_i)$ を子に送る。
また、 $s_i$ を親に送る代わりに、 $(c,s)=(c,s_i)$ を署名として出力する。

パラメータ生成

(Parameter Generation) $Pg$ アルゴリズムが $\kappa$ -bit素数である $q$ が位数である群 $\mathbb{G}=\langle g \rangle$ を作る。
また、2つのハッシュ関数 $H_0,H_1:\{0,1\}^*\mathbb{Z}_q$ を選び、 $par\leftarrow(\mathbb{G},g,q,H_0,H_1)$ を出力する。

鍵生成

鍵生成アルゴリズム(Key Generation) $Kg(par)$ が $sk\xleftarrow{\char36 }\mathbb{Z}_q$ を抽出し、 $y\leftarrow g^{sk}$ を計算する。
その時、 $r\xleftarrow{\char36 }\mathbb{Z}_q$ を選び、 $s\leftarrow r + H_1(g^r,y)$ を計算することにより、 $\pi = (c,s)$ を持っていることの証明を作る。
$pk\leftarrow (y,\pi)$ と $sk$ を出力する。

署名

$S_i$ は $Sign(par,sk_i,m,\mathcal{T})$ をインプットしている。

アナウンスメント

$S_i$ がリーダーならば、署名セッションssidの識別子を持つ子にアナウンスメントを送り、プロトコルを開始する。
$S_i$ がリーダーでないならば、アナウンスメントを待ち、 $\mathcal{T}$ にいる子に送る。

コミットメントフェーズ

$\mathcal{C}_i$ を $\mathcal{T}$ 内の $S_i$ の子の集団とする。 $S_i$ は $j\in \mathcal{C}_i$ に対する全ての $(t_j,PK_j)$ を受け取るまで待つ。
もし $S_i$ に子がいなければ、スキップされる。
$S_i$ は $r_i\xleftarrow{\char36 }\mathbb{Z}_q$ を選び、 $pk_i=(y_i,\pi_i)$ に対して $t_i\leftarrow g^{r_i}\cdot\prod_{j\in \mathcal{C}_i}t_j$ と $PK_i\leftarrow y_i\cdot\prod_{j\in \mathcal{C}_i}PK_j$ を計算する。
もし $S_i$ がリーダーでないならば、 $t_i$ を親に送る。
もし $S_i$ がリーダーならばチャレンジへ進む。

チャレンジ

もし $S_i$ がリーダーならば $\bar t\leftarrow t_i$ と $PK\leftarrow PK_i$ をセットし、 $c\leftarrow H_0(\bar{t},m)$ を計算し、 $(\bar{t},PK)$ を子に送る。
もし $S_i$ がリーダーでないならば、メッセージ $(\bar{t},PK)$ を待ち、 $c\leftarrow H_0(\bar{t},m)$ を計算し、 $(\bar{t},PK)$ を子に送る。

レスポンス

$S_i$ は $j\in \mathcal{C}_i$ に対する全ての $s_i$ を待ち、 $s_i\leftarrow r_i+c\cdot sk_i+\sum_{j\in \mathcal{C}_i}s_j$ を計算する。
$s_i$ を親に送り、 $S_i$ がrootでない限り、 $S_i$ は $s \leftarrow s_i$ をセットし、 $\sigma \leftarrow (c,s)$ を出力する。

鍵集約

公開鍵の集合 $\mathcal{PK}$ をインプットしている $KAg$ が、全ての $(y,(c,s))\in \mathcal{PK}$ に対して、 $c = H_1(g^sy^{-c},y)$ を確かめる。
集約された公開鍵 $PK\leftarrow \prod_{(y,\pi)\in \mathcal{PK}}y$

検証

公開鍵 $PK$ 、署名 $\sigma = (c,s)$ 、メッセージ $m$ をインプットしている $Vf$ が $c \stackrel{?}{=}H_0(g^s \cdot PK^{-c},m)$ を検証する。

CoSiプロトコルの安全性の証明の欠陥

一般的なシュノア署名の安全性の証明技術では、CoSiプロトコルの安全性証明に失敗することを理解することで、CoSiプロトコルの安全性の証明の欠陥を直感的に理解できる。

DL仮定の下でのシュノア署名の安全性の証明では、リダクションがランダムに $(c,s)$ を選び、 $g^s=t \cdot pk^c$ が成り立つように $t$ を選択し、ランダムオラクル $H(t,m)=c$ を計算する。
次に分岐補題を適用して、攻撃者から2つの偽造品を取り出し、 $pk=y$ を計算する。

シュノア署名では、ハッシュに含まれる最終的な $\bar t$ は、1人の署名者が決定するが、CoSiプロトコルでは、ハッシュに含まれる最終的な $\bar t$ は、個々の署名者の $t_i$ の積である。
だから、署名クエリのリーダーが誠実な署名者でない場合、攻撃者はシミュレータよりも先に、最終的な $\bar t$ を知ることになり、シミュレータがランダムオラクル $H(\bar{t},m)=c$ を計算することを防げる。

OMDL仮定の下での安全性を証明すれば、この状況を回避できるように思われる。以下にその直感的な議論を述べるが、その中に欠陥があり、CoSiプロトコルの安全性が示されないことになる。

まず、シミュレータは離散対数オラクルを用いて、署名クエリをシミュレートできる。署名クエリをシミュレートする際に、最初のターゲットポイントを $y_0$ を公開鍵 $pk=y_0$ として使用し、ターゲットポイント $y_1,...,y_n$ を値 $t_1,...,t_n$ として使用する。
分岐補題を用いて、 $pk=y_0$ の離散対数を抽出し、この値と前の離散対数クエリに対する応答に基づいて、他のターゲット $t_1,...,t_n$ の離散対数を計算する。
全体として、このリダクションではDLオラクルへの $n$ 回のクエリだけを用いて、 $n+1$ 個のターゲットポイントの離散対数を計算する。

この議論の欠陥とは、分岐補題により、シミュレータが既に $t_i$ を算出しているが、最終的な値である $\bar t$ をまだ受け取っていない時点まで巻き戻される可能性があることを見落としている点だ。
問題は、攻撃者が2回目の実行時に $\bar t$ を選択し、シミュレータが二回目のDLクエリを実行しなければならず、OMDL問題を解決するチャンスを失う可能性があることだ。

この問題により、CoSiの安全性の証明は無効になる。