Pseudorandom generator theorem

A distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non-negligibleadvantage. Formally, a family of distributions D_n is pseudorandom if for any polynomial size circuit C, and any ε inversely polynomial in n

|Prob_x∈U [C(x)=1] − Prob_x∈D [C(x)=1] | ≤ ε.

A function G_l: {0,1}^l → {0,1}^m, where l < m is a pseudorandom generator if:

• G_l can be computed in time polynomial in l
• G_l(x) is pseudorandom, when x is uniformly random.

It can be shown that if there is a pseudorandom generator G_l: {0,1}^l → {0,1}^l+1, i.e. a generator that adds only one pseudorandom bit, then for any m = poly(l), there is a pseudorandom generator G'_l: {0,1}^l → {0,1}^m.

The idea of the proof is as follows: first s bits from uniform distribution U_l are picked and used as the seed to the first instance of G_l, which is known to be a pseudorandom generator. Next, the output of the first instance of G_l is divided into two parts: first l bits are fed into the second instance of G_l as a seed, while the last bit becomes the first bit of the output. Repeating this process for m times yields an output of m pseudorandom bits.

Se puede demostrar que tal G' _l , que consta de m instancias de G _l , es de hecho un generador pseudoaleatorio utilizando un enfoque híbrido y una prueba por contradicción como sigue:

Consideremos m+1 distribuciones intermedias H _i : 0  ≤  i  ≤  m , donde los primeros i bits se eligen de la distribución uniforme y los últimos m − i bits se eligen de la salida de G' _l . Por lo tanto, H ₀ es la salida completa de G' _l y H _m es una verdadera distribución uniforme U _m . En consecuencia, las distribuciones H _i y H _i+1 se diferenciarán en un solo bit (bit número i +1).

Ahora bien, supongamos que G' _l no es una distribución pseudoaleatoria; es decir, existe algún circuito C que puede distinguir entre G' _l y U _m con una ventaja ε  =  1/ poly ( l ). En otras palabras, este circuito puede distinguir entre H ₀ y H _m . Por lo tanto, existe tal i tal que el circuito C puede distinguir entre H _i y H _i+1 por al menos ε / m . Nótese que, dado que m es polinomial en l , entonces ε / m también es polinomial en l y sigue siendo una ventaja no despreciable.

Ahora bien, supongamos que se nos dan l+1 bits que son la salida de G _l o extraídos de una distribución uniforme. Reutilicemos el método de construir grandes generadores pseudoaleatorios a partir de instancias de G _l y construyamos una cadena de bits pseudoaleatorios de longitud m − i − 1 de la misma manera que se construyó G' _l anteriormente, utilizando los primeros l bits dados como semilla. Luego, creemos una cadena que consta de i bits extraídos de la distribución uniforme, concatenados con el último de los bits dados, seguidos de los m − i − 1 bits creados. La salida resultante es H _i o H _i+1 , ya que el bit i+1 se extrae de la distribución uniforme o de G _l . Dado que, por supuesto, podemos distinguir entre H _i y H _i+1 con una ventaja no despreciable , entonces podemos distinguir entre U y G _l , lo que implica que G _l no es un generador pseudoaleatorio, lo cual contradice la hipótesis. QED

Ahora, ilustremos que si existe, el circuito para distinguir entre G _l y U _l+1 no tiene que lanzar monedas al azar. Como mostramos anteriormente, si existe un circuito C para distinguir entre G' _l y U _m , donde m  = poly ( l ), ​​entonces existe un circuito C' para distinguir entre G _l y U _l+1 que utiliza i bits aleatorios. Para este circuito C' : | Prob _{u, s} [ C' ( u ₁ ,...,u _i ,G _l ( s )) = 1 ] − Prob _{u, y} [ C' ( u ₁ ,>,...,u _i ,y ) = 1] | ≥ ε / m ,   

donde u es una cadena de i bits aleatorios uniformes, s es una cadena de l bits aleatorios uniformes e y es una cadena de l + 1 bits aleatorios uniformes.

Entonces,

Prob _u [ | Prob _s [ C' ( u ₁ ,...,u _i ,G _l ( s )) = 1] - Prob _y [ C' ( u ₁ ,...,u _i ,y ) = 1] | ] ≥ ε  /  m ;

Lo que significa que existe una cadena fija u de i bits que puede usarse como un "consejo" al circuito C' para distinguir entre G _l y U _l+1 .

Aquí se presenta un resumen de la demostración. Para ver las demostraciones detalladas, consulte las referencias.

1. Dado z=f(x), adivina el bit b. 2. Ejecutar C en zb 3. SI C(zb)=1 4. Salida b 5. DE LO CONTRARIO 6. Salida 1-b