En la teoría de la complejidad computacional y la criptografía , la existencia de generadores pseudoaleatorios está relacionada con la existencia de funciones unidireccionales a través de una serie de teoremas, denominados colectivamente como el teorema del generador pseudoaleatorio .
Una distribución se considera pseudoaleatoria si ningún cálculo eficiente puede distinguirla de la distribución uniforme verdadera por una ventaja no despreciable . Formalmente, una familia de distribuciones D n es pseudoaleatoria si para cualquier circuito de tamaño polinómico C y cualquier ε inversamente polinómico en n
Una función G l : {0,1} l → {0,1} m , donde l < m es un generador pseudoaleatorio si:
Se puede demostrar que si existe un generador pseudoaleatorio G l : {0,1} l → {0,1} l +1 , es decir, un generador que agrega solo un bit pseudoaleatorio, entonces para cualquier m = poly ( l ), existe un generador pseudoaleatorio G' l : {0,1} l → {0,1} m .
La idea de la prueba es la siguiente: se seleccionan los primeros s bits de la distribución uniforme U l y se utilizan como semilla para la primera instancia de G l , que se sabe que es un generador pseudoaleatorio. A continuación, la salida de la primera instancia de G l se divide en dos partes: los primeros l bits se introducen en la segunda instancia de G l como semilla, mientras que el último bit se convierte en el primer bit de la salida. Al repetir este proceso m veces se obtiene una salida de m bits pseudoaleatorios.
Se puede demostrar que dicho 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 de la siguiente manera:
Considérense 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 0 es la salida completa de G' l y H m es una verdadera distribución uniforme U m . Por lo tanto, las distribuciones H i y H i+1 serán diferentes en solo un bit (bit número i +1).
Ahora, 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 0 y H m . Por lo tanto, existe tal i que el circuito C puede distinguir entre H i y H i+1 por al menos ε / m . Nótese que, dado que m son polinomiales en l , entonces ε / m también es polinomial en l y sigue siendo una ventaja no despreciable.
Ahora, supongamos que se nos dan l+1 bits que son la salida de G l o una distribución uniforme. Reutilicemos el enfoque 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 consiste en i bits extraídos de la distribución uniforme, concatenados con el último de los bits dados, seguido 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 suposición 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 que es una contradicción con 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 arriba, 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 usa i bits aleatorios. Para este circuito C' : | Prob u, s [ C' ( u 1 ,..., u i , G l ( s )) = 1 ] − Prob u, y [ C' ( u 1 ,>,..., u i , y ) = 1] | ≥ ε / m ,
donde u es una cadena de i bits uniformemente aleatorios, s es una cadena de l bits uniformemente aleatorios e y es una cadena de l +1 bits uniformemente aleatorios.
Entonces,
Prob u [ | Prob s [ C' ( u 1 ,..., u i , G l ( s )) = 1] - Prob y [ C' ( u 1 ,..., 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 .
La existencia de generadores pseudoaleatorios está relacionada con la existencia de funciones unidireccionales y predicados de núcleo duro . Formalmente, los generadores pseudoaleatorios existen si y solo si existen funciones unidireccionales, o
PRG ↔ OWF
Intuitivamente, las funciones unidireccionales son funciones que son fáciles de calcular y difíciles de invertir. En otras palabras, la complejidad (o tamaño del circuito) de la función es mucho menor que la de su inversa. Formalmente: Una función ƒ: {0,1} n → {0,1} n es ( S , ε ) unidireccional si para cualquier circuito C de tamaño ≤ S ,
Prob[ƒ( C (ƒ( x ))) = ƒ( x )] ≤ ε .
Además, ƒ es una función unidireccional si
Función B : {0,1} n → {0,1} es un predicado de núcleo duro para la función ƒ si
En otras palabras, es difícil predecir B ( x ) a partir de la función ƒ( x ).
A continuación se ofrece un esquema de la prueba. Consulte las referencias para ver pruebas detalladas.
Consideremos un generador pseudoaleatorio G l : {0,1} l → {0,1} 2l . Creemos la siguiente función unidireccional ƒ: {0,1} n → {0,1} n que utiliza la primera mitad de la salida de G l como su salida. Formalmente,
ƒ( x , y ) → Gl ( x )
Una observación clave que justifica dicha selección es que el tamaño del universo preimagen es 2 n y es una fracción insignificante de la imagen de la función de tamaño 2 2n .
Para demostrar que ƒ es de hecho una función unidireccional, construyamos un argumento por contradicción. Supongamos que existe un circuito C que invierte ƒ con ventaja ε :
Problema[ƒ( C (ƒ( x , y ))) = ƒ( x , y )] > ε
Entonces podemos crear el siguiente algoritmo que distinguirá G l de uniforme, lo que contradice la hipótesis. El algoritmo tomaría una entrada de 2n bits z y calcularía ( x , y ) = C ( z ). Si G l ( x ) = z el algoritmo lo aceptaría, de lo contrario lo rechazaría.
Ahora bien, si z se extrae de una distribución uniforme, la probabilidad de que el algoritmo anterior acepte es ≤ 1/2 l , ya que el tamaño de la preimagen es 1/2 l del tamaño de la imagen. Sin embargo, si z se extrajo de la salida de G l, entonces la probabilidad de aceptación es > ε suponiendo la existencia del circuito C . Por lo tanto, la ventaja que tiene el circuito C para distinguir entre la distribución uniforme U y la salida de G l es > ε − 1/2 l , lo cual no es despreciable y, por lo tanto, contradice nuestra suposición de que G l es un generador pseudoaleatorio. QED
Para este caso demostramos una versión más débil del teorema:
Permutación unidireccional → generador pseudoaleatorio
Una permutación unidireccional es una función unidireccional que también es una permutación de los bits de entrada. Se puede construir un generador pseudoaleatorio a partir de la permutación unidireccional ƒ de la siguiente manera:
G l : {0,1} l →{0,1} l +1 = ƒ( x ). B ( x ), donde B es un predicado de núcleo duro de ƒ y "." es un operador de concatenación. Nótese que, según el teorema demostrado anteriormente, solo es necesario demostrar la existencia de un generador que agrega solo un bit pseudoaleatorio.
En primer lugar, demostremos que si B es un predicado estricto de ƒ entonces G l es, en efecto, pseudoaleatorio. Nuevamente, utilizaremos un argumento por contradicción.
Supongamos que G l no es un generador pseudoaleatorio; es decir, existe un circuito C de tamaño polinomial que distingue G l ( x ) = ƒ( x ). B ( x ) de U l+1 con ventaja ≥ ε , donde ε no es despreciable. Nótese que, dado que ƒ( x ) es una permutación, entonces si x se extrae de una distribución uniforme, entonces también lo es si ƒ( x ). Por lo tanto, U l+1 es equivalente a ƒ( x ). b , donde b es un bit extraído independientemente de una distribución uniforme. Formalmente,
Prob x~U [ C ( G ( x ))=1] − Prob x~U,b~U [ C ( xb )=1] ≥ ε
Construyamos el siguiente algoritmo C' :
1. Dado z=f(x), supongamos que el bit b2. Ejecutar C en zb3. SI C(zb)=14. salida b5. DEMÁS6. salida 1-b
Dado el resultado de ƒ, el algoritmo primero adivina el bit b lanzando una moneda al azar, es decir, Prob[ b = 0] = Prob[ b = 1] = 0,5. Luego, se ejecuta el algoritmo (circuito) C en f(x).b y si el resultado es 1, se devuelve b ; de lo contrario, se devuelve el inverso de b .
Entonces la probabilidad de que C' adivine B ( x ) correctamente es:
Prob x~U [ C' ( z )= B ( x )] =
Prob[ b = B ( x )∧C ( zb ) =1] + Prob[ b ≠ B ( x ) ∧C ( zb )=0] =
Prob[ b = B ( x )]⋅Prob[ C ( zb )=1 | b = B ( x )] + Prob[ b ≠ B ( x )]⋅Prob[ C ( zb )=0 | b ≠ B ( x )] =
1/2⋅Prob[ C ( zb )=1 | b = B ( x )] + 1/2⋅Prob[ C ( zb )=0 | b ≠ B ( x )] =
(1−1/2)⋅Prob[ C ( zb )=1 | b = B ( x )] + 1/2⋅(1−Prob[ C ( zb )=1 | b ≠ B ( x )]) =
1/2+Prob z.b~G(x) [ C ( zb )=1] − 1/2⋅(Prob[ C ( zb )=1 | b = B ( x )]+Prob[ C ( zb )=1 | b ≠ B ( x )]) =
1/2+Prob z.b~G(x) [ C ( zb )=1] − Prob z.b~U [ C ( zb )=1] ≥ 1/2+ ε
Esto implica que el circuito C' puede predecir B ( x ) con una probabilidad mayor que 1/2 + ε , lo que significa que B no puede ser un predicado duro para ƒ y la hipótesis se contradice. QED
El esquema de la prueba es el siguiente:
Si ƒ{0,1} n →{0,1} n es una permutación unidireccional, entonces también lo es ƒ'{0,1} 2n →{0,1} 2n , donde ƒ'( x , y )=ƒ( x ). y por definición. Entonces B ( x , y )= x ⋅ y es un predicado de núcleo duro para ƒ', donde ⋅ es un producto escalar vectorial . Para demostrar que es de hecho de núcleo duro, supongamos lo contrario y mostremos una contradicción con la hipótesis de que ƒ es unidireccional. Si B no es un predicado de núcleo duro, entonces existe un circuito C que lo predice, por lo que
Prob x,y [ C (ƒ( x ), y )= x ⋅ y ] ≥ 1/2+ ε . Ese hecho se puede utilizar para recuperar x mediante la construcción inteligente de permutaciones y que aíslan bits en x . De hecho, para una fracción constante de x , existe un algoritmo de tiempo polinomial que enumera O (1/ ε 2 ) candidatos que incluyen todos los x válidos . Por lo tanto, un algoritmo puede invertir ƒ( x ) en tiempo polinomial para una fracción no despreciable de x , lo que contradice la hipótesis.