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

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

p(n) = n + 2 のとき、G(s) = (f²(s), hc(f(s)), hc(s)).

• 真の乱数 R = (r, σ₀, σ₁)
• ハイブリッドH = (f(s), hc(s), σ₁)
• 疑似乱数 G = (f²(s), hc(f(s)), hc(s))

RとHは、(r, σ₀)と(f(s), hc(s))が区別できないので、区別できない。
HとGは、(s, σ₁)と(f(s), hc(s))が区別できないので、区別できない。
よって、RとGは区別できない。

定理(PSG2)の証明

任意のPPT識別者DのGに対する識別利得をε(n)とおく：
ε(n) = Pr[ s ← {0,1}ⁿ : D(G(s)) = 1 ] - Pr[ r ← {0,1}^p(n) : D(r) = 1 ] .

0以上p'(n)以下の各jについて、以下のハイブリッド分布H_n^jを考える：
H_n^j:

• s_j ← {0,1}^n+j
• i ∈ [(j+1)..p'(n)] :
  • (s'_i-1, σ_i-1) = s_i-1
  • s_i = (G₀(s'_i-1), σ_i-1)
• return s_p'(n)

あきらかに、
ε(n) = Pr[ s' ← H_n⁰ : D(s') = 1 ] - Pr[ s' ← H_n^p'(n) : D(s') = 1 ] .

ここで、Gに対する識別者Dを用いて、G₀に対する識別者D₀を以下のように構成する：
D₀: w (∈{0,1}ⁿ⁺¹)を入力として、

• j ← [1..p'(n)], σ_j ← {0,1}^j-1, s_j ← (w,σ_j)      /* n+j ビット */
• i ∈ [(j+1)..p'(n)] :
  • (s'_i-1, σ_i-1) = s_i-1
  • s_i = (G₀(s'_i-1), σ_i-1)
• return D(s_p'(n))

識別者D₀の解析:

• D₀への入力が、w ← {0,1}ⁿ⁺¹ のとき、
  • j として J が選択されたら、
    • s_J は n+J ビットのランダム文字列。
    • よって、s_p'(n)の分布はH_n^Jの分布と同一。
• 以上より、
• Pr[ w ← {0,1}ⁿ⁺¹ : D₀(w) = 1 ]
  • = 1/p'(n) Σ_J=1..p'(n) Pr[ w ← {0,1}ⁿ : D₀(w) = 1 j=J ]
  • = 1/p'(n) Σ_J=1..p'(n) Pr[ s' ← H_n^J : D(s') = 1 ].

• D₀への入力が、w = G₀(s) (s ← {0,1}ⁿ) のとき、
  • j として J が選択されたら、
    • s_J は n+(J-1) ビットのランダム文字列に一回G₀を適用した形。
    • よって、s_p'(n)の分布はH_n^J-1の分布と同一。
• 以上より、
• Pr[ s ← {0,1}ⁿ : D₀(G₀(s)) = 1 ]
  • = 1/p'(n) Σ_J=1..p'(n) Pr[ s ← {0,1}ⁿ : D₀(G₀(s)) = 1 j=J ]
  • = 1/p'(n) Σ_J=1..p'(n) Pr[ s' ← H_n^J-1 : D(s') = 1 ]
  • = 1/p'(n) Σ_{J=0..(p'(n)-1)} Pr[ s' ← H_n^J : D(s') = 1 ].

よって、D₀のG₀に対する識別利得は

• 1/p'(n) ｜ Pr[ s' ← H_n^p'(n) : D(s') = 1 ] - Pr[ s' ← H_n⁰ : D(s') = 1 ] ｜
  • = ε(n)/p'(n)

に等しいが、G₀は疑似乱数生成器なので、これはネグリジブル。よって、ε(n)もネグリジブルである。
Q.E.D.

上へ

---