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

お知らせ
Table of Content

はじめに

この記事では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_iSign(par,sk_i,m,\mathcal{T})をインプットしている。

アナウンスメント

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

コミットメントフェーズ

\mathcal{C}_i\mathcal{T}内のS_iの子の集団とする。S_ij\in \mathcal{C}_iに対する全ての(t_j,PK_j)を受け取るまで待つ。
もしS_iに子がいなければ、スキップされる。
S_ir_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_jPK_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_iPK\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_ij\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_is \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をインプットしているVfc \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の安全性の証明は無効になる。

MuSigの安全性の証明の欠陥

CoSiとMuSigでは、鍵集約の手順が異なる。MuSigでは、鍵集約の際に、個々の鍵を単純に掛け合わせるのではなく、ハッシュ関数の出力に上げていて、OMDL仮定のもとでの安全性の証明を提示している。

しかし、上記の欠陥の問題点は、不正な鍵の攻撃とは関係なく、多くの署名のクエリが並行して行われ、巻き戻しによって署名者の秘密鍵を知ることがリダクションによって強制され得ることにある。実際、上記の攻撃はMuSigにも適用でき、MuSigの安全性が証明される可能性は非常に低いことを証明している。

まとめ

この指摘を受け、MuSigのプロトコルは改良されました。[2]に紹介されているので興味のある方は是非御覧ください。暗号の複雑なアルゴリズムの安全性証明は非常に煩雑で、査読済みの論文であってもこのように「証明」がしばしば反証され撤回されることがあるということは興味深いです。

参考文献

[1] https://eprint.iacr.org/2018/417.pdf
[2] https://eprint.iacr.org/2018/068.pdf
[3] https://github.com/dedis/cothority/blob/main/cosi/README.md

タイトルとURLをコピーしました