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

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

sを乱数とするとき、G(s) = (f(s), hc(s))が乱数と区別がつかないことをいいたい。

• sが乱数のとき、f(s)も乱数である。
• さらに、f(s)がわかっても、hcはハードコア述語なので、hc(s)は0なのか1なのかわからない。

定理(PSG)の証明

任意のPPT識別者Dの、疑似乱数生成器候補 G(s) = (f(s), hc(s)) に対する識別利得ε(n)は、
ε(n) := Pr[ s ← {0,1}ⁿ : D(G(s)) = 1 ] - Pr[ r ← {0,1}ⁿ⁺¹ : D(r) = 1 ]
=　Pr[ s ← {0,1}ⁿ : D(f(s),hc(s)) = 1 ] - Pr[ r ← {0,1}ⁿ⁺¹ : D(r) = 1 ].

ここで、
Pr[ r ← {0,1}ⁿ⁺¹ : D(r) = 1 ] = Pr[ r← {0,1}ⁿ, r' ← {0,1} : D(r,r') = 1 ]
= Pr[ s ← {0,1}ⁿ, r' ← {0,1} : D(f(s),r') = 1 ]
= 1/2 Pr[ s ← {0,1}ⁿ : D(f(s),hc(s)) = 1 ] + 1/2 Pr[ s ← {0,1}ⁿ : D(f(s),1-hc(s)) = 1 ]

よって、
ε(n) = 1/2 (Pr[ s ← {0,1}ⁿ : D(f(s),hc(s)) = 1 ] - Pr[ s ← {0,1}ⁿ : D(f(s),1-hc(s)) = 1 ]). 　　--(1)

識別者Dを用いて、ハードコア述語hcに対するPPT識別者Aを構成する。
識別者A: y (=f(s)) を入力として、

• r' ← {0,1}
• (y, r') を入力としてDを起動：
  • Dが 1 を出力したら r' を、そうでないならば 1 - r' を出力して停止。

識別者Aの解析:
識別者Aの（ハードコア述語hcに対する）識別利得は、定義より、
Pr[ s ← {0,1}ⁿ : A(f(s)) = hc(s) ] - 1/2
= 1/2 Pr[ s ← {0,1}ⁿ : A(f(s)) = r' | r' = hc(s) ] + 1/2 Pr[ s ← {0,1}ⁿ : A(f(s)) = 1-r' | r' = 1-hc(s) ] - 1/2
= 1/2 (Pr[ s ← {0,1}ⁿ : D(f(s),hc(s)) = 1 ] + Pr[ s ← {0,1}ⁿ : D(f(s),1-hc(s)) ≠ 1 ]) - 1/2
= 1/2 (Pr[ s ← {0,1}ⁿ : D(f(s),hc(s)) = 1 ] - Pr[ s ← {0,1}ⁿ : D(f(s),1-hc(s)) = 1 ])
= ε(n).

hcはハードコア述語なのでε(n)はネグリジブルである。
Q.E.D.

上へ

---