Processing math: 96%
Now you are in the subtree of Lecture Notes public knowledge tree. 

Лемма о получении генератора из перестановки

Лемма 2

β(x) - трудный бит для f(x)xf(x)β(x) - генератор.

Доказательство


β можно угадать f(x)β(x) можно отличить от y.
Dn(y)=(Cn(y1n)yn+1)
y случайное Dn угадывает с вероятностью 12.
y=f(x)β(x)Dn угадает с вероятностью 12+1p(n)


f(x)β(x) умеем отличать от y можно предсказать β(x) по f(x).
y можно представить в виде f(x)r.

D(f(x)1)D(f(x)1)01D(f(x)0)0random1D(f(x)0)10random

Введем p0,p1,q0,q1,r0,r1,s0,s1 - вероятности в соответствующих условиях того, что β(x)=0 и β(x)=1.

Например: r1=Pr{β(x)=1, D(f(x)0)=1, D(f(x)1)=0}.

Pr\{C_n(f(x)) = \beta(x)\} = \frac{1}{2}(p_0 + p_1) + q_1 + r_0 + \frac{1}{2}(s_0 + s_1) \boldsymbol{\circeq} \\ = Pr\{D(f(x)r) = 1\} = (s_0 + s_1) + \frac{1}{2}(r_0 + r_1) + \frac{1}{2}(q_0 + q_1) = Pr\{D(f(x)\beta(x)) = 1\} = \\ = (s_0 + s_1) + r_0 + q_1 = \frac{1}{2}(r_0 - r_1) + \frac{1}{2}(q_1 - q_0) > \varepsilon = \\ \boldsymbol{\circeq} \frac{1}{2}(p_0 + p_1) + \frac{1}{2}(q_1 + q_0) + \frac{1}{2}(r_0 + r_1) + \frac{1}{2}(r_0 - r_1) + \frac{1}{2}(s_0 + s_1) = \\ = \frac{1}{2} + \frac{1}{2}(q_1 - q_0) + \frac{1}{2}(r_0 - r_1) > \frac{1}{2} + \varepsilon