定理CPA暗号の証明 - 暗号理論教室

定理(CPA暗号)の証明のアイデア

構成(CPA暗号)の暗号文は、

• c = (m + (hc_i(f_i^l-1(r)), hc_i(f_i^l-2(r)), ..., hc(r)), f_i^l(r)).

(hc_i(f_i^l-1(r)), hc_i(f_i^l-2(r)), ..., hc(r),f_i^l(r))は、
真の乱数(p, s) と区別がつかない。（p,sはそれぞれlビット、nビット）

よって、cは

• c' = (m + p, s)

と区別がつかない。

c'は完全にmを隠しているので、cも（効率的な攻撃者に対しは）mを隠す。

定理(CPA暗号)の証明

構成(CPA暗号)をΠとし、Πに対する任意の効率的な攻撃者をAとする。
Aの成功確率 ｜ Pr[CPA_Π,A(n) = 1] - 1/2 ｜ がネグリジブルであることを示したい。

まず、Game G₀を定義する。Game G₀は、試行 CPA_Π,A(n)をΠ=構成(CPA暗号)として具体化したものである：

Game G₀:

• (pk, sk) = (i, t_i) ← G(1ⁿ)
• pk=iを入力としてAを起動する。
  • Aから同じ長さlの2つのメッセージからなるチャレンジクエリ(m₀,m₁)を受け取ったら、
    • 0または1をランダムに選択し、bとする。
    • m_bをpkで暗号化し、c*をえる：
      • r ← {0,1}ⁿ
      • f_i(r), f_i²(r), ..., f_i^l(r) を計算。
      • p = ( hc_i(f_i^l-1(r)), hc_i(f_i^l-2(r)), ..., hc(r) )
      • c* = (m_b + p, f_i^l(r))
    • c*をチャレンジクエリに対する応答として返す。
• Aが出力b'で終了したら、b =^? b' の１ビットを出力とする。

Game G₁では、Game G₀で疑似乱数であるpを真の乱数に変更する：
Game G₁:

• (pk, sk) = (i, t_i) ← G(1ⁿ)
• pk=iを入力としてAを起動する。
  • Aから同じ長さlの2つのメッセージからなるチャレンジクエリ(m₀,m₁)を受け取ったら、
    • 0または1をランダムに選択し、bとする。
    • m_bをpkで暗号化し、c*をえる：
      • r ← {0,1}ⁿ
      • p ← {0,1}^l
      • c* = (m_b + p, r)
    • c*をチャレンジクエリに対する応答として返す。
• Aが出力b'で終了したら、b =^? b' の１ビットを出力とする。

主張1
Pr[ G₁ = 1] = 1/2.
証明 pが真にランダムなので、c* = (m_b + p, r) は、b=0のときも b=1のときも、(l+n)ビットの乱数である。
よって、Aのview（Aが入手するすべての情報）はbと統計的に独立である。
よって、Aの出力もbと統計的に独立なので、b = b' となる確率は1/2である。Q.E.D.

主張2
Pr[G₁ = 1] - Pr[G₀= 1] はネグリジブルである。
証明 攻撃者Aを用いて、構成(PSG3)の疑似乱数生成器Gに対する識別者Dを構成する：
識別者D: 長さ(n+l)ビットの文字列(w, p)を入力として、インデックスiを補助入力として、

• pk=iを入力としてAを起動する。
  • Aから同じ長さlの2つのメッセージからなるチャレンジクエリ(m₀,m₁)を受け取ったら、
    • 0または1をランダムに選択し、bとする。
    • m_bをpkで暗号化し、c*をえる：
      • c* = (m_b + p, w)
    • c*をチャレンジクエリに対する応答として返す。
• Aが出力b'で終了したら、b =^? b' の１ビットを出力とする。

[識別者Dの解析]:

• 入力(w,p)が疑似乱数(f_i^l(r), hc_i(f_i^l-1(r)), hc_i(f_i^l-2(r)), ..., hc(r))のとき、
  • （識別者D内のAが受け取るc*） ≡ （G₀におけるc*）
• 入力(w,p)が真のn+lビット乱数のとき、
  • （識別者D内のAが受け取るc*） ≡ （G₁におけるc*）

よって、識別者Dの識別利得は

• ｜ Pr[G₁(1ⁿ) = 1] - Pr[G₀(1ⁿ) = 1] ｜

に等しく、Gは疑似乱数生成器なので、これはネグリジブルである。Q.E.D.

主張1より、

• ｜ Pr[CPA_Π,A(n) = 1] - 1/2 ｜ = ｜Pr[G₀ = 1] - Pr[G₁ = 1] ｜

であり、主張2よりこれはネグリジブルである。
Q.E.D.

上へ

---