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

定理(NMinRO)の証明

構成(CCAinRO)に対する任意のPPT攻撃者を(F,A)とする。Aを用いてシミュレーターA*を構成する。

シミュレーターA*: (pk=i,π)を入力として、

• x* ← π(1ⁿ), r ← {0,1}ⁿ, α = (f_i(r), G(r)+x*, H(r,x*))
• α' ← A(pk,π,α)
• return α'

Exp₁:

• G,H ← {0,1}^∞, (i,t_i) ← Genf(1ⁿ), pk = (i,G,H), π ← F(pk),
• x ← π, r ← {0,1}ⁿ, α = (a=f_i(r), w=G(r)+x, b=H(r,x)),
• α' = (a',w',b') ← A(pk,π,α), r' = f_i^-1(a'), x' = w' + G(r')
• H(r',x') ≠^? b' : x' = ⊥
• return ρ(x, x')      // ε(n) = Pr[Exp₁ = 1]

ε(n)の分析:

• Case 1: α' = α. x'=xとなるので、定義より ρ(x,x') = 0.
• Case 2: α' ≠ α, AはHオラクルに(r',x')を問い合わせていない.
  • α' ≠ αより、x' ≠ x または r' ≠ r. よって、H(r',x')はAにとって一様ランダム。よって、Pr[ρ(x,x') = 1] ≦ Pr[b' = H(r',x')] = 2^-n.
• Case 3: α' ≠ α, AはHオラクルに(r',x')を問い合わせている. λ₁ := Pr[Case3].
  • Case 3-(i): AはGまたはHオラクルに r を問い合わせていない. λ₂ := Pr[Case3-(i),ρ(x,x') = 1 | Case3].
    • このとき、AにとってG(r)は一様ランダム。よって、wにxの情報はなく、xはsupp(π)上一様分布。
  • Case 3-(ii): AはGまたはHオラクルに r を問い合わせている.
    • このときAはf_iの一方向性を破っているので、あるネグリジブルな関数ηがあって、Pr[Case3-(ii)] ≦ η(n).

以上より、ε(n) ≦ 2^-n + λ₁ ( λ₂ + η(n) ).

Exp₂:

• G,H ← {0,1}^∞, (i,t_i) ← Genf(1ⁿ), pk = (i,G,H), π ← F(pk),
• x ← π, x* ← π, r ← {0,1}ⁿ, α = (a=f_i(r), w=G(r)+x*, b=H(r,x*)),
• α' = (a',w',b') ← A(pk,π,α), r' = f_i^-1(a'), x' = w' + G(r')
• H(r',x') ≠^? b' : x' = ⊥
• return ρ(x, x')      // ε*(n) = Pr[Exp₂ = 1]

Exp₂においてもAのviewは、Exp₁におけるそれと全く同じ。よって、

• 上のケースわけは、Exp₂においても、全く同じ確率分布で行われる。
• Case 3-(i)では、G(r)はAにとって一様ランダムなので　Pr[ρ(x,x')] = Pr[ρ(x*,x')].
• よって、ε*(n) ≧ λ₁ λ₂.

したがって、ε(n) - ε*(n) ≦ 2^-n + λ₁ η(n).
Q.E.D.

---