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

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

構成(CPAinRO)の暗号文は、

• c = (f_i(r), G(r)+m).

f_iは一方向置換なので、cをもらっても r はわからない。
よって、ランダムオラクルモデルのもと、G(r)は攻撃者にとって（f_i(r)と独立な）未知の乱数 s。

よって、cは攻撃者にとって、

• c = (f_i(r), s+m).

これはmを完全に隠す。

定理(CPAinRO)の証明

構成(CPAinRO)に対する任意の効率的な攻撃者をAとする。Aの成功確率を 1/2 + ε とおく。
εがネグリジブルであることを示したい。

Aを用いてトラップドア置換の攻撃者Bを構成する：
攻撃者B: y*(=f_i(r*))を入力として、インデックスiを補助入力として、

• pk=(i,G)を入力としてAを起動する。
  • AからGオラクルに対する問い合わせrを受け取ったら、
    • y* = f_i(r)ならば、rを出力して終了。
    • G[r]が未定義ならば、g ← {0,1}^l, G[r] = g
    • g = G[r]を返答する。
  • Aからチャレンジクエリ(m₀,m₁)を受け取ったら、
    • s ← {0,1}^l, c* = (y*, s)      // 本来は、s = G(r*) であるべき。
  • c*を返答する。
• Aが終了したら、終了する。

[攻撃者Bの解析]:
AskRを 『AがGオラクルにr*をたずねる』というイベントとする：

• AskRがおきないうちは、BのAに対するシミュレーションは完ぺき。(sがテキトウであることがバレナイ）
• AskRがおきれば、Bは直ちに成功する。
• AskRが最後までおきなかったら、Aの成功確率は高々1/2である。(c*はm₀やm₁と関係ない！）

よって、

• 1/2+ε(n) = Pr[Aが成功する ｜ AskR] Pr[AskR] + Pr[Aが成功する ｜ ￢AskR] Pr[￢AskR]
  • ≦ Pr[AskR] + 1/2 ≦ Pr[Bが成功する] + 1/2

よって、

• ε(n)　≦　Pr[Bが成功する].

ところが、仮定よりf_iは一方向置換なので右辺はネグリジブル、よってε(n)もネグリジブルである。
Q.E.D.

上へ

---