定理(GQ2)の証明のアイデア

pk = (N, e, X), sk = (N, e, x)に関する、GQプロトコルのトランスクリプトは
  • コミットメント (Y), チャレンジ (c), レスポンス (z).
これについて、
  • ze? YXc (mod N)
が成り立てば、検証者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を得る。
        • ※ zie ≡ WiW0ci.
      • 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