定理(GQ2)の証明のアイデア
pk = (N, e, X), sk = (N, e, x)に関する、GQプロトコルのトランスクリプトは
- コミットメント (Y), チャレンジ (c), レスポンス (z).
これについて、
が成り立てば、検証者Vは受理する。
コンカレントな攻撃者Aを用いて、ワンモアRSA問題に対する攻撃者Bを構成できることを示す。
攻撃者Bは、
- Aに渡す公開鍵X=W0や証明者クローンとしてのコミットメントWiを挑戦オラクルから入手する。
- 証明者クローンとしてのレスポンスziは逆変換オラクルから入手する。
- Aがなりすましに成功するならば、定理(GQ1)の証明と同じように、
- 公開鍵X=W0に対応するRSA問題の解w0を計算し、
- それによってすべての問題Wiの解wiを計算する。
定理(GQ2)の証明
GQプロトコルに対する任意のコンカレントな攻撃者をA=(A1 , A2)とする。
Aを用いて、primeGenRSAに関する試行OneMoreRSAにおける攻撃者Bを構成する:
B: (e, N)を入力として、
- 挑戦オラクルに問題を要求し、W0を得る。
- n = 0.
- pk = (N, e, W0)を入力として、A1を起動する。
- A1が新しい証明者クローンを要求したら、
- n = n + 1, 挑戦オラクルに問題を要求し、Wnを得る。
- Wnを返す。
- A1が i 番目の証明者クローンにチャレンジcを発したら、
- ci = c
- 逆変換オラクルに WiW0ci を問い合わせ、返答ziを得る。
- ziを返す。
- A1の出力stを受け取り、A2をstを入力として起動する。
- ※ ここで、A2(st)は決定的としてよい。(stにランダムテープが含まれているとしてよい。)
- A2からY*を受け取ったら、c*1 ← {0,1}l を返す。
- A2からz*1を受け取ったら、
- z*1e ≡? Y*W0c*1 (mod N) でないならばアボート。
- A2を再びstを入力として起動する。
- A2からY*を受け取り、c*2 ← {0,1}l を返す。 ※ A2(st)は決定的なので、必ず前と同じY*.
- A2からz*2を受け取ったら、
- z*2e ≡? Y*W0c*2 (mod N) でないならばアボート。
- c1 = c2 ならばアボート。
- (z*1/z*2)e ≡ W0c*1-c*2 (mod N) より、w0e ≡ W0 (mod N) となるw0を計算。
- ※ gcd(c*1 - c*2, e) = 1 なので 補題(CS)を適用できる。
- i ∈ [1..n] : wi = zi w0-ci.
- ※ wie ≡ zie w0-ci e ≡ (Wi W0ci) W0-ci ≡ Wi.
- (w0, w1, ... , wn) を出力して停止。
[Bの解析]:
明らかに、Bがアボートしなければ、その出力(w0, w1, ... , wn)はワンモアRSA問題(e,N,X)の正しい解。よって、
- Pr[BがワンモアRSA問題を解く] = Pr[Bがアボートしない].
一方、BのAに対するシミュレーションは完ぺきなので、
- 『 Bがアボートしない 』 ≡ 『 証明者Q=A2(st)に対し、イベントRESが成り立つ 』。
よって、補題(Reset)より
- Pr[Bがアボートしない] = Pr[RES] ≧ (Pr[Aがなりすましに成功] - 1/2l)2.
以上より、
- Pr[BがワンモアRSA問題を解く] ≧ (Pr[Aがなりすましに成功] - 1/2l)2.
仮定より、
- l はスーパーログなので、1/2lはネグリジブル。
- Pr[BがワンモアRSA問題を解く]もネグリジブル。
よって、Pr[Aがなりすましに成功]もネグリジブル。(ただし、ネグリジブルの「度合い」は半分。)
Q.E.D.
最終更新:2009年11月07日 17:33