定理(GQ1)の証明 - 暗号理論教室

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

pk = (N, e, X), sk = (N, e, x)に関する、GQプロトコルのトランスクリプトは

• コミットメント (Y), チャレンジ (c), レスポンス (z).

これについて、

• z^e ≡^? YX^c (mod N)

が成り立てば、検証者Vは受理する。

[トランスクリプトから秘密鍵xの（大事な）情報が漏れないこと]
トランスクリプトは、秘密鍵x を用いなくても、

• z' ← Z_N*, c' ← {0,1}^l, Y' = z'^e X^-c' mod N

と生成できる。
よって、トランスクリプトは（秘密鍵xをもたない）誰にでも生成できる。

[秘密鍵xをもたなければ、証明者になりすませないこと]
攻撃者Aがなりすましを試み、コミットメントYを送った時点を考える。
Aが（無視できない確率で）なりすましに成功するならば、Aは、
2通りのc₁、c₂に対し、それぞれ、妥当な応答z₁、z₂を返せるはず：

• z₁^e ≡ YX^c1 (mod N),
• z₂^e ≡ YX^c2 (mod N).

このとき、

• (z₁/z₂)^e ≡ X^c1-c2 (mod N).

これから、w^e ≡ X (mod N) となるwを効率的に計算できる。
つまり、Aは秘密鍵w=xを知っている。

定理(GQ1)の証明

GQプロトコルに対する任意の受動的な攻撃者をA=(A₁ , A₂)とする。
Aを用いて、primeGenRSAが生成する(e,N)について、
RSA問題(e,N,X)を解くアルゴリズムBを構成する：

B: (e, N, X)を入力として、

• ※ Bは w^e ≡ X (mod N) となるwを計算したい。
• pk = (e, N, X) を入力としてA₁を起動する：
  • A₁ がトランスクリプトを要求したら、
    • z' ← Z_N*, c' ← {0,1}^l, Y' = z'^e X^-c' mod N
    • (Y', c', z')を返す。
• A₁の出力stを受け取り、A₂をstを入力として起動する。
• ※ ここで、A₂(st)は決定的としてよい。（stに必要なランダムテープが含まれているとしてよいから。）
  • A₂からYを受け取ったら、c₁ ← {0,1}^l を返す。
  • A₂からz₁を受け取ったら、
    • z₁^e ≡^? YX^c1 (mod N) でないならば、アボート。
• A₂を再びstを入力として起動する。
  • A₂から（先と同一の）Yを受け取り、c₂ ← {0,1}^l を返す。　
  • A₂からz₂を受け取ったら、
    • z₂^e ≡^? YX^c2 (mod N) でないならば、アボート。
• c₁ = c₂ ならばアボート。
• (z₁/z₂)^e ≡ X^c1-c2 (mod N) より、w^e ≡ X (mod N) となるwを計算し、出力する。
• ※ gcd(c₁ - c₂, e) = 1 なので 補題(CS)を適用できる。

[Bの解析]:
明らかに、Bがアボートしなければ、その出力wはRSA問題(e,N,X)の正しい解。よって、

• Pr[BがRSA問題を解く] = Pr[Bがアボートしない].

一方、BのAに対するシミュレーションは完ぺきなので、

• 『 Bがアボートしない 』　≡　 『 証明者Q=A₂(st)に対し、イベントRESが成り立つ 』。

よって、補題(Reset)より

• Pr[Bがアボートしない] = Pr[RES] ≧ (Pr[Aがなりすましに成功] - 1/2^l)².

以上より、

• Pr[BがRSA問題を解く] ≧ (Pr[Aがなりすましに成功] - 1/2^l)².

仮定より、

• l はスーパーログなので、1/2^lはネグリジブル。
• Pr[BがRSA問題を解く]もネグリジブル。

よって、Pr[Aがなりすましに成功]もネグリジブル。（ただし、ネグリジブルの「度合い」は半分。）

Q.E.D.

上へ

---