はじめに
この記事ではCoSiプロトコルの安全性の証明の欠陥を応用した、2ラウンドのMuSigが安全でないことの証明[1]を紹介します。
まず、記号の定義を説明し、CoSiプロトコルの説明、CoSiプロトコルの安全性の証明の欠陥を述べ、それを応用してMuSig安全性の証明の欠陥を述べます。
記号の定義
素数位数の群を
とし、
を最大
回呼び出されうる離散対数オラクルとする。
攻撃者の
を
とし、この値は
と
によってランダムに定まる。
が離散対数問題を解くとは、最大
時間で解けてかつ、
となること。
また、上のような攻撃者が存在しない時、離散対数は-困難である。
DL仮定とは、離散対数問題を解くのが困難だとする仮定。
また、攻撃者の
を
とし、この値は
と
によってランダムに定まる。
がn-one-more離散対数問題を解くとは、最大
時間で解けてかつ、
となること。
また、上のような攻撃者が存在しない時、n-one-more離散対数は-困難である。
OMDL仮定とは、one-more離散対数問題を解くのが困難だとする仮定。
要するに一つの離散対数問題を解くのも、n個の離散対数問題を解くのも同様に難しいという仮定である。
CoSiプロトコルの説明
CoSi プロトコルは 非常に巨大であることがありうる分散化されたグループが独立したサーバーで動いている時に、効率的にシュノア署名を生成するためのアルゴリズムである。概要は [3] のドキュメントを参照せよ。
アナウンス->コミットメント->チャレンジ->レスポンスという4つのフェーズが存在する。これをツリー状に分岐したパスを用いて各パーティに届けることで効率的に署名が構成できるとされる。
署名者に対して、秘密鍵は
、公開鍵は
で定義される。
署名者がリーダーならば、
を親に送る代わりに、
を子に送る。
また、を親に送る代わりに、
を署名として出力する。
パラメータ生成
(Parameter Generation)アルゴリズムが
-bit素数である
が位数である群
を作る。
また、2つのハッシュ関数を選び、
を出力する。
鍵生成
鍵生成アルゴリズム(Key Generation)が
を抽出し、
を計算する。
その時、を選び、
を計算することにより、
を持っていることの証明を作る。
と
を出力する。
署名
は
をインプットしている。
アナウンスメント
がリーダーならば、署名セッションssidの識別子を持つ子にアナウンスメントを送り、プロトコルを開始する。
がリーダーでないならば、アナウンスメントを待ち、
にいる子に送る。
コミットメントフェーズ
を
内の
の子の集団とする。
は
に対する全ての
を受け取るまで待つ。
もしに子がいなければ、スキップされる。
は
を選び、
に対して
と
を計算する。
もしがリーダーでないならば、
を親に送る。
もしがリーダーならばチャレンジへ進む。
チャレンジ
もしがリーダーならば
と
をセットし、
を計算し、
を子に送る。
もしがリーダーでないならば、メッセージ
を待ち、
を計算し、
を子に送る。
レスポンス
は
に対する全ての
を待ち、
を計算する。
を親に送り、
がrootでない限り、
は
をセットし、
を出力する。
鍵集約
公開鍵の集合をインプットしている
が、全ての
に対して、
を確かめる。
集約された公開鍵
検証
公開鍵、署名
、メッセージ
をインプットしている
が
を検証する。
CoSiプロトコルの安全性の証明の欠陥
一般的なシュノア署名の安全性の証明技術では、CoSiプロトコルの安全性証明に失敗することを理解することで、CoSiプロトコルの安全性の証明の欠陥を直感的に理解できる。
DL仮定の下でのシュノア署名の安全性の証明では、リダクションがランダムにを選び、
が成り立つように
を選択し、ランダムオラクル
を計算する。
次に分岐補題を適用して、攻撃者から2つの偽造品を取り出し、を計算する。
シュノア署名では、ハッシュに含まれる最終的なは、1人の署名者が決定するが、CoSiプロトコルでは、ハッシュに含まれる最終的な
は、個々の署名者の
の積である。
だから、署名クエリのリーダーが誠実な署名者でない場合、攻撃者はシミュレータよりも先に、最終的なを知ることになり、シミュレータがランダムオラクル
を計算することを防げる。
OMDL仮定の下での安全性を証明すれば、この状況を回避できるように思われる。以下にその直感的な議論を述べるが、その中に欠陥があり、CoSiプロトコルの安全性が示されないことになる。
まず、シミュレータは離散対数オラクルを用いて、署名クエリをシミュレートできる。署名クエリをシミュレートする際に、最初のターゲットポイントをを公開鍵
として使用し、ターゲットポイント
を値
として使用する。
分岐補題を用いて、の離散対数を抽出し、この値と前の離散対数クエリに対する応答に基づいて、他のターゲット
の離散対数を計算する。
全体として、このリダクションではDLオラクルへの回のクエリだけを用いて、
個のターゲットポイントの離散対数を計算する。
この議論の欠陥とは、分岐補題により、シミュレータが既にを算出しているが、最終的な値である
をまだ受け取っていない時点まで巻き戻される可能性があることを見落としている点だ。
問題は、攻撃者が2回目の実行時にを選択し、シミュレータが二回目の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