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 teorema del generador pseudoaleatorio .
Introducción
Pseudoaleatoriedad
Una distribución se considera pseudoaleatoria si ningún cálculo eficiente puede distinguirla de la verdadera distribución uniforme por una ventaja no despreciable . Formalmente, una familia de distribuciones D n es pseudoaleatoria si para cualquier circuito C de tamaño polinomial , y cualquier polinomio ε inversamente en n
- | Prob x ∈ U [ C ( x ) = 1] - Prob x ∈ D [ C ( x ) = 1] | ≤ ε .
Generadores pseudoaleatorios
Una función G l : {0,1} l → {0,1} m , donde l < m es un generador pseudoaleatorio si:
- G l se puede calcular en polinomio de tiempo en l
- G l ( x ) es pseudoaleatorio, cuando x es uniformemente aleatorio.
Un bit pseudoaleatorio adicional implica polinomialmente más bits pseudoaleatorios
Se puede demostrar que si hay 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 ), hay un generador pseudoaleatorio G ' l : {0,1} l → {0,1} m .
La idea de la prueba es el siguiente: primeros s bits de distribución uniforme U l se recogen y se utilizan como la 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 alimentan a la segunda instancia de G l como semilla, mientras que el último bit se convierte en el primer bit de la salida. La repetición de este proceso por m veces produce una salida de m bits pseudoaleatorios.
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 prueba por contradicción como sigue:
Considere distribuciones intermedias m + 1 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 tanto, H 0 es la salida total 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 un solo bit (número de bit i +1).
Ahora, suponga 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 / poli ( 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 . Tenga en cuenta que dado que m son polinomios en l , entonces ε / m también es polinomio en l y sigue siendo una ventaja no despreciable.
Ahora, suponga que se nos dan 1 + 1 bits que son salida de G 1 o extraídos de 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 G ' l se construyó anteriormente usando los primeros l bits dados como semilla. Luego, creemos una cadena que consta de i bits extraídos de uniforme, concatenados con el último de los bits dados, seguido de los bits m − i − 1 creados . La salida resultante es H i o H i + 1 , ya que el bit i + 1 se extrae de uniforme o de G l . Dado que, por supuesto, podemos distinguir entre H i e 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 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 = poli ( 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.
Luego,
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" para el circuito C ' para distinguir entre G 1 y U 1 + 1 .
Existencia de generadores pseudoaleatorios
La existencia de generadores pseudoaleatorios está relacionada con la existencia de funciones unidireccionales y predicados de núcleo duro . Formalmente, existen generadores pseudoaleatorios si y solo si existen funciones unidireccionales, o
PRG ↔ OWF
Definiciones
Funciones unidireccionales
Las funciones intuitivamente unidireccionales son funciones 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, f es una función unidireccional si
- ƒ se puede calcular en tiempo polinomial
- ƒ es ( poli ( n ), 1 / poli ( n )) unidireccional
Predicado de núcleo duro
Función B : {0,1} n → {0,1} es un predicado de núcleo duro para la función ƒ si
- B se puede calcular en tiempo polinomial
- para cualquier circuito C de tamaño polinómico y cualquier ε = 1 / poli ( n ) no despreciable , Prob x ~ U [ C (ƒ ( x )) = B ( x )] ≤ 1/2 + ε
En otras palabras, es difícil predecir B ( x ) a partir de la función ƒ ( x ).
Prueba
Aquí se da un resumen de la prueba. Consulte las referencias para obtener pruebas detalladas.
PRG → OWF
Considere un generador pseudoaleatorio G l : {0,1} l → {0,1} 2l . Creemos la siguiente función unidireccional ƒ: {0,1} n → {0,1} n que usa la primera mitad de la salida de G l como salida. Formalmente,
ƒ ( x , y ) → G l ( x )
Una observación clave que justifica tal selección es que la imagen de la función es de tamaño 2 n y es una fracción insignificante del universo preimagen de tamaño 2 2n .
Para demostrar que f es de hecho una función unidireccional, construyamos un argumento por contradicción. Suponga que existe un circuito C que invierte ƒ con ventaja ε :
Prob [ƒ ( C (ƒ ( x , y ))) = ƒ ( x , y )]> ε
Luego, podemos crear el siguiente algoritmo que distinguirá G l del 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, 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 imagen es 1/2 l del tamaño de la preimagen. Sin embargo, si z se extrajo de la salida de G l entonces la probabilidad de aceptación es> ε por supuesto de la existencia de circuito C . Por lo tanto, la ventaja que tiene el circuito C al distinguir entre la U uniforme y la salida de G l es> ε - 1/2 l , que no es despreciable y, por lo tanto, contradice nuestra suposición de que G l es un generador pseudoaleatorio. QED
OWF → PRG
Para este caso probamos 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 una permutación unidireccional ƒ de la siguiente manera:
G l : {0,1} l → {0,1} l +1 = ƒ ( x ). B ( x ), donde B es un predicado fundamental de f y "." es un operador de concatenación. Tenga en cuenta que, según el teorema demostrado anteriormente, solo es necesario mostrar la existencia de un generador que agrega solo un bit pseudoaleatorio.
Predicado de núcleo duro → PRG
Primero, demostremos que si B es un predicado de núcleo duro para ƒ, entonces G l es de hecho pseudoaleatorio. Nuevamente, usaremos un argumento por contradicción.
Suponga 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. Tenga en cuenta que, dado que ƒ ( x ) es una permutación, entonces si x se extrae de una distribución uniforme, entonces también si ƒ ( x ). Por tanto, U l + 1 es equivalente a ƒ ( x ). b , donde b es un bit extraído independientemente de una distribución uniforme. Formalmente,
Problema x ~ U [ C ( G ( x )) = 1] - Problema x ~ U, b ~ U [ C ( xb ) = 1] ≥ ε
Construyamos el siguiente algoritmo C ' :
1. Dado z = f (x) adivinar el bit b 2. Ejecute C en zb3. SI C (zb) = 14. salida b5. ELSE6. salida 1-b
Dada la salida de ƒ, el algoritmo primero adivina el bit b lanzando una moneda al azar, es decir , Prob [ b = 0] = Prob [ b = 1] = 0.5. Luego, el algoritmo (circuito) C se ejecuta en f (x) .by si el resultado es 1, entonces se genera b ; de lo contrario, se devuelve el inverso de b .
Entonces la probabilidad de que C ' adivine B ( x ) correctamente es:
Problema 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 | segundo ≠ 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 fundamental para ƒ y la hipótesis se contradice. QED
OWP → predicado de núcleo duro
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 realmente duro, supongamos lo contrario y muestremos una contradicción con la hipótesis de que f es unidireccional. Si B no es un predicado de núcleo duro, entonces existe un circuito C que lo predice, entonces
Prob x, y [ C (ƒ ( x ), y ) = x ⋅ y ] ≥ 1/2 + ε . Ese hecho puede usarse para recuperar x construyendo inteligentemente 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 / & epsilon 2 ) candidatos que incluyen todas las x válidas . Por lo tanto, un algoritmo puede invertir f ( x ) en tiempo polinomial para una fracción no despreciable de x , lo que contradice la hipótesis.
Referencias
- W. Diffie, ME Hellman. "Nuevas direcciones en criptografía". IEEE Transactions on Information Theory , IT-22, págs. 644–654, 1976.
- AC Yao. "Teoría y aplicación de las funciones de la trampilla". 23º Simposio del IEEE sobre fundamentos de la informática , págs. 80–91, 1982.
- M. Blum y S. Micali "Cómo generar secuencias criptográficamente fuertes de bits pseudoaleatorios". SIAM Journal on Computing , v13, págs. 850–864, 1984.
- J. Hastad, R. Impagliazzo, LA Levin y M. Luby. "Un generador pseudoaleatorio de cualquier función unidireccional". SIAM Journal on Computing , v28 n4, pp.-1364-1396, 1999.