Loading [MathJax]/extensions/tex2jax.js

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

お知らせ
Table of Contents

はじめに

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

記号の定義

素数位数qqの群をG=g\mathbb{G}=\langle g \rangleとし、Odlog()\mathcal{O}^{dlog}(\cdot)を最大nn回呼び出されうる離散対数オラクルとする。
攻撃者A\mathcal{A}ADVGdlADV^{dl}_G
Pr[y=gx:y$G,x$A(y)]Pr[y=g^x:y\xleftarrow{\char36 }\mathbb{G},x \xleftarrow{\char36 }\mathcal{A}(y)]とし、この値はA\mathcal{A}yyによってランダムに定まる。
A(τ,ϵ)\mathcal{A}(\tau,\epsilon)が離散対数問題を解くとは、最大τ\tau時間で解けてかつ、ADVGdlϵADV^{dl}_G\geq \epsilonとなること。
また、上のような攻撃者が存在しない時、離散対数は(τ,ϵ)(\tau,\epsilon)-困難である。
DL仮定とは、離散対数問題を解くのが困難だとする仮定。
また、攻撃者A\mathcal{A}ADVGnomdlADV^{n-omdl}_\mathbb{G}
Pr[i=0nyi=gxi:(y0,...,yn)$Gn+1,(x0,...,xn)$AOdlog()(y0,...,yn)]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)]とし、この値はA\mathcal{A}y0,...,yny_0,...,y_nによってランダムに定まる。
A(τ,ϵ)\mathcal{A}(\tau,\epsilon)がn-one-more離散対数問題を解くとは、最大τ\tau時間で解けてかつ、ADVGnomdlϵADV^{n-omdl}_\mathbb{G}\geq \epsilonとなること。
また、上のような攻撃者が存在しない時、n-one-more離散対数は(τ,ϵ)(\tau,\epsilon)-困難である。
OMDL仮定とは、one-more離散対数問題を解くのが困難だとする仮定。
要するに一つの離散対数問題を解くのも、n個の離散対数問題を解くのも同様に難しいという仮定である。

CoSiプロトコルの説明

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

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

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

パラメータ生成

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

鍵生成

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

署名

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

アナウンスメント

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

コミットメントフェーズ

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

チャレンジ

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

レスポンス

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

鍵集約

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

検証

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

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

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

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

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

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

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

この議論の欠陥とは、分岐補題により、シミュレータが既にtit_iを算出しているが、最終的な値であるtˉ\bar tをまだ受け取っていない時点まで巻き戻される可能性があることを見落としている点だ。
問題は、攻撃者が2回目の実行時にtˉ\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をコピーしました