定理(PSF)の証明のアイデア
n=2とする。x = 01 における値F(k, 01)は（kを知らない）識別者には乱数に見える。
実際、
- F(k, 01) = G1(G0(k)) ～ G1(k') ～ k''.
定理(PSF)の証明
任意のPPT識別者Dの疑似ランダム関数候補Fに対する識別利得をε(n)とおく：
ε(n) :=
Pr[k ← {0,1}
n : D
F(k,・)(1
n) = 1] - Pr[f ← Fnc(n,n) : D
f(・)(1
n) = 1]
0以上n以下の各iについて、以下のハイブリッド分布Hniを考える：
Hni:
- レベルiの全ての(2i個の)ノードそれぞれに、独立なnビットランダム文字列を割り当てる。
- レベル(i+1)以降の各ノードには構成(PSF)と全く同様にしてnビット文字列を割り当てる。
- すなわち、ラベルxをもつノードに文字列vxが割り当てられていたら、その2つの子ノードには文字列vx0 := G0(vx)と文字列vx1 := G1(vx)をそれぞれ割り当てる。
明らかに、
- Hn0において葉ノードに割り当てられる文字列の分布は、関数F(k,・)の出力分布と同一。
- Hnnにおけるそれは、真のランダム関数f (← Fnc(n,n))の出力分布と同一。
よって、
- ε(n) = ｜ Pr[ DHnn(1n) = 1] - Pr[ DHn0(1n) = 1] ｜.
Fに対する上記識別者D(1n)の計算ステップ数の上界をt(n)とおく。
Dを用いて、疑似乱数生成器Gに対する識別者D'を構成する：
D': t個の2nビット文字列v1=(v1,0,v1,1),・・・,vt=(vt,0,vt,1)を入力として、
- i ← [0..(n-1)]
- 1nを入力としてDを起動：
- Dがオラクルにx = (x1,・・・,xn)における関数値を問い合わせたら：
- ラベル(x1,・・・,xi)が指定するレベルiのノードvに注目する。
- ノードvの子ノードにまだ文字列が割り当てられていないならば、入力からまだ使われていない2nビット文字列vjを取り出し、vj,0とvj,1をそれぞれvの2つの子ノードに割り当てる。
- 以降、ラベルx=(x1,・・・,xn)が指定するレベルnのノードにむけて、構成(PSF)と同じ方法で子ノードに文字列を割り当てていく。
- ラベルxが指定するレベルnのノードに割り当てられた文字列を、xにおける関数値としてDに返す。
- Dが停止したら、その出力を自身の出力として停止する。
識別者Dの解析:
- Dへの入力である、各2nビット文字列viがすべて真のランダム文字列であるとき、
- 確率変数iとしてIが選択されたとすると、D'が構成する2分木の分布はHnI+1のそれと同一である。
- (レベルI+1の各ノードに真のランダム文字列が割り当てられる。)
- よって、
- Pr[v1,...,vt ← {0,1}2n : D'(v1,...,vt) = 1 ｜ i = I] = Pr[DHnI+1(1n) = 1].
- よって、
- Pr[v1,...,vt ← {0,1}2n : D'(v1,...,vt) = 1]
- = 1/n ΣI=0..(n-1) Pr[DHnI+1(1n) = 1]
- = 1/n ΣI=1..n Pr[DHnI(1n) = 1].
- Dへの入力である、各2nビット文字列viがすべて疑似ランダム文字列G(si)であるとき、
- 確率変数iとしてIが選択されたとすると、D'が構成する2分木の分布はHnIのそれと同一である。
- (レベルIの各ノードに真のランダム文字列が割り当てられる。)
- よって、
- Pr[v1=G(s1),...,vt=G(st) : D'(v1,...,vt) = 1 ｜ i = I] = Pr[DHnI(1n) = 1].
- よって、
- Pr[v1=G(s1),...,vt=G(st) : D'(v1,...,vt) = 1]
- = 1/n ΣI=0..(n-1) Pr[DHnI(1n) = 1].
したがって、D'の識別利得は
- ｜ Pr[v1,...,vt ← {0,1}2n : D'(v1,...,vt) = 1] - Pr[v1=G(s1),...,vt=G(st) : D'(v1,...,vt) = 1] ｜
- = 1/n ｜ Pr[DHnn(1n) = 1] - Pr[DHn0(1n) = 1] ｜
- = ε(n)/n.
Gは疑似乱数生成器なのでこれはネグリジブル。よって、Dの識別利得ε(n)もネグリジブルである。
Q.E.D.
最終更新：2009年10月01日 16:05
