Generador pseudoaleatorio

Término utilizado en informática teórica y criptografía.

En informática teórica y criptografía , un generador pseudoaleatorio (PRG) para una clase de pruebas estadísticas es un procedimiento determinista que asigna una semilla aleatoria a una cadena pseudoaleatoria más larga , de modo que ninguna prueba estadística de la clase pueda distinguir entre la salida del generador y la distribución uniforme. La semilla aleatoria en sí es típicamente una cadena binaria corta extraída de la distribución uniforme .

En la literatura se han considerado muchas clases diferentes de pruebas estadísticas, entre ellas la clase de todos los circuitos booleanos de un tamaño determinado. No se sabe si existen buenos generadores pseudoaleatorios para esta clase, pero se sabe que su existencia es en cierto sentido equivalente a los límites inferiores de circuitos (no probados) en la teoría de la complejidad computacional . Por lo tanto, la construcción de generadores pseudoaleatorios para la clase de circuitos booleanos de un tamaño determinado se basa en supuestos de dureza actualmente no probados.

Definición

Sea una clase de funciones. Estas funciones son las pruebas estadísticas que el generador pseudoaleatorio intentará engañar, y normalmente son algoritmos . En ocasiones, las pruebas estadísticas también se denominan adversarios o distinguidores . ^[1] La notación en el codominio de las funciones es la estrella de Kleene . ${\displaystyle {\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0,1\}^{*}\}}$

Una función con es un generador pseudoaleatorio contra con sesgo si, para cada en , la distancia estadística entre las distribuciones y es como máximo , donde es la distribución uniforme en . ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$ ${\displaystyle \ell <n}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \varepsilon }$ ${\displaystyle A}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A(G(U_{\ell }))}$ ${\displaystyle A(U_{n})}$ ${\displaystyle \varepsilon }$ ${\displaystyle U_{k}}$ ${\displaystyle \{0,1\}^{k}}$

La cantidad se llama longitud de la semilla y la cantidad se llama estiramiento del generador pseudoaleatorio. ${\displaystyle \ell }$ ${\displaystyle n-\ell }$

Un generador pseudoaleatorio contra una familia de adversarios con sesgo es una familia de generadores pseudoaleatorios , donde es un generador pseudoaleatorio contra con sesgo y longitud de semilla . ${\displaystyle ({\mathcal {A}}_{n})_{n\in \mathbb {N} }}$ ${\displaystyle \varepsilon (n)}$ ${\displaystyle (G_{n})_{n\in \mathbb {N} }}$ ${\displaystyle G_{n}:\{0,1\}^{\ell (n)}\to \{0,1\}^{n}}$ ${\displaystyle {\mathcal {A}}_{n}}$ ${\displaystyle \varepsilon (n)}$ ${\displaystyle \ell (n)}$

En la mayoría de las aplicaciones, la familia representa algún modelo de cálculo o algún conjunto de algoritmos , y uno está interesado en diseñar un generador pseudoaleatorio con una longitud de semilla y un sesgo pequeños, y tal que la salida del generador pueda calcularse mediante el mismo tipo de algoritmo. ${\displaystyle {\mathcal {A}}}$

En criptografía

En criptografía , la clase suele estar formada por todos los circuitos de tamaño polinomial en la entrada y con un único bit de salida, y lo que interesa es diseñar generadores pseudoaleatorios que sean computables mediante un algoritmo de tiempo polinomial y cuyo sesgo sea despreciable en el tamaño del circuito. Estos generadores pseudoaleatorios a veces se denominan generadores pseudoaleatorios criptográficamente seguros (CSPRG) . ${\displaystyle {\mathcal {A}}}$

No se sabe si existen generadores pseudoaleatorios criptográficamente seguros. Probar que existen es difícil ya que su existencia implica P ≠ NP , lo cual es una creencia generalizada pero un problema notoriamente abierto. La existencia de generadores pseudoaleatorios criptográficamente seguros es ampliamente aceptada. Esto se debe a que se ha demostrado que los generadores pseudoaleatorios se pueden construir a partir de cualquier función unidireccional que se crea que existe. ^{[2] [3]} Los generadores pseudoaleatorios son necesarios para muchas aplicaciones en criptografía .

El teorema del generador pseudoaleatorio muestra que existen generadores pseudoaleatorios criptográficamente seguros si y solo si existen funciones unidireccionales .

Usos

Los generadores pseudoaleatorios tienen numerosas aplicaciones en criptografía. Por ejemplo, los generadores pseudoaleatorios proporcionan un análogo eficiente de los blocs de notas de un solo uso . Es bien sabido que para cifrar un mensaje m de forma que el texto cifrado no proporcione información sobre el texto simple, la clave k utilizada debe ser aleatoria en cadenas de longitud |m|. El cifrado perfectamente seguro es muy costoso en términos de longitud de clave. La longitud de clave se puede reducir significativamente utilizando un generador pseudoaleatorio si la seguridad perfecta se reemplaza por seguridad semántica . Las construcciones comunes de cifrados de flujo se basan en generadores pseudoaleatorios.

Los generadores pseudoaleatorios también pueden utilizarse para construir criptosistemas de clave simétrica , en los que se puede cifrar de forma segura una gran cantidad de mensajes con la misma clave. Esta construcción puede basarse en una familia de funciones pseudoaleatorias , que generaliza el concepto de generador pseudoaleatorio.

En la década de 1980, las simulaciones en física comenzaron a utilizar generadores pseudoaleatorios para producir secuencias con miles de millones de elementos y, a fines de esa década, se había desarrollado evidencia de que algunos generadores comunes arrojaban resultados incorrectos en casos como las propiedades de transición de fase del modelo 3D de Ising y las formas de agregados limitados por difusión. Luego, en la década de 1990, se utilizaron varias idealizaciones de simulaciones físicas (basadas en paseos aleatorios , funciones de correlación , localización de estados propios, etc.) como pruebas de generadores pseudoaleatorios. ^[4]

Pruebas

El NIST anunció las pruebas de aleatoriedad SP800-22 para comprobar si un generador pseudoaleatorio produce bits aleatorios de alta calidad. Yongge Wang demostró que las pruebas del NIST no son suficientes para detectar generadores pseudoaleatorios débiles y desarrolló la técnica de prueba basada en la distancia estadística LILtest. ^[5]

Para desaleatorización

Una de las principales aplicaciones de los generadores pseudoaleatorios es la desaleatorización de los cálculos basados ​​en la aleatoriedad, sin corromper el resultado del cálculo. Los ordenadores físicos son máquinas deterministas y obtener una aleatoriedad real puede ser un desafío. Los generadores pseudoaleatorios se pueden utilizar para simular de manera eficiente algoritmos aleatorios utilizando poca o ninguna aleatoriedad. En tales aplicaciones, la clase describe el algoritmo aleatorio o la clase de algoritmos aleatorios que se desea simular, y el objetivo es diseñar un generador pseudoaleatorio "eficientemente computable" cuya longitud de semilla sea lo más corta posible. Si se desea una desaleatorización completa, se procede a una simulación completamente determinista reemplazando la entrada aleatoria del algoritmo aleatorio con la cadena pseudoaleatoria producida por el generador pseudoaleatorio. La simulación hace esto para todas las semillas posibles y promedia la salida de las diversas ejecuciones del algoritmo aleatorio de una manera adecuada. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

Construcciones

Para tiempo polinomial

Una pregunta fundamental en la teoría de la complejidad computacional es si todos los algoritmos aleatorizados en tiempo polinomial para problemas de decisión pueden simularse determinísticamente en tiempo polinomial. La existencia de una simulación de este tipo implicaría que BPP = P . Para realizar dicha simulación, es suficiente construir generadores pseudoaleatorios contra la familia F de todos los circuitos de tamaño s ( n ) cuyas entradas tienen longitud n y salida un solo bit, donde s ( n ) es un polinomio arbitrario, la longitud de semilla del generador pseudoaleatorio es O(log n ) y su sesgo es ⅓.

En 1991, Noam Nisan y Avi Wigderson proporcionaron un generador pseudoaleatorio candidato con estas propiedades. En 1997, Russell Impagliazzo y Avi Wigderson demostraron que la construcción de Nisan y Wigderson es un generador pseudoaleatorio suponiendo que existe un problema de decisión que puede calcularse en tiempo 2 ^{O( n )} en entradas de longitud n pero requiere circuitos de tamaño 2 ^{Ω( n )} .

Para el espacio logarítmico

Si bien se necesitan suposiciones no probadas sobre la complejidad del circuito para demostrar que el generador de Nisan-Wigderson funciona para máquinas limitadas en el tiempo, es natural restringir aún más la clase de pruebas estadísticas de modo que no tengamos que depender de tales suposiciones no probadas. Una clase para la que se ha hecho esto es la clase de máquinas cuyo espacio de trabajo está limitado por . Usando un truco de cuadratura repetida conocido como teorema de Savitch , es fácil demostrar que cada cálculo probabilístico del espacio logarítmico se puede simular en el espacio . Noam Nisan (1992) demostró que esta desaleatorización en realidad se puede lograr con un generador pseudoaleatorio de longitud de semilla que engaña a todas las máquinas del espacio. Saks y Zhou (1999) han utilizado el generador de Nisan para demostrar que el cálculo probabilístico del espacio logarítmico se puede simular de forma determinista en el espacio . Este resultado fue mejorado por William Hoza en 2021 a espacio . ${\displaystyle O(\log n)}$ ${\displaystyle O(\log ^{2}n)}$ ${\displaystyle O(\log ^{2}n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log ^{1.5}n)}$ ${\displaystyle O(\log ^{1.5}n/{\sqrt {\log \log n}})}$

Para funciones lineales

Cuando las pruebas estadísticas consisten en todas las funciones lineales multivariadas sobre un campo finito , se habla de generadores con sesgo épsilon . La construcción de Naor y Naor (1990) logra una longitud de semilla de , que es óptima hasta factores constantes. Los generadores pseudoaleatorios para funciones lineales a menudo sirven como un bloque de construcción para generadores pseudoaleatorios más complicados. ${\displaystyle \mathbb {F} }$ ${\displaystyle \ell =\log n+O(\log(\epsilon ^{-1}))}$

Para polinomios

Viola (2008) demuestra que al tomar la suma de los polinomios de grado 1 y 2 de los generadores de sesgo pequeño , se obtienen polinomios de grado 2. La longitud de la semilla es . ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle \ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))}$

Para circuitos de profundidad constante

Circuitos de profundidad constante que producen un único bit de salida. ^{[ cita requerida ]}

Limitaciones de probabilidad

No se ha demostrado la existencia de los generadores pseudoaleatorios utilizados en criptografía y desaleatorización algorítmica universal, aunque se cree ampliamente que existen ^{[ cita requerida ]} . Las pruebas de su existencia implicarían pruebas de límites inferiores en la complejidad del circuito de ciertas funciones explícitas. Dichos límites inferiores del circuito no se pueden demostrar en el marco de pruebas naturales que supongan la existencia de variantes más fuertes de generadores pseudoaleatorios criptográficos. ^[6]

Referencias

1. Katz, Jonathan (6 de noviembre de 2014). Introducción a la criptografía moderna . Lindell, Yehuda (segunda edición). Boca Raton. ISBN 9781466570269.OCLC 893721520  .{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
2. HÅstad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1 de enero de 1999). "Un generador pseudoaleatorio a partir de cualquier función unidireccional". Revista SIAM de Computación . 28 (4): 1364–1396. doi :10.1137/S0097539793244708.
3. Katz, Jonathan; Lindell, Yehuda (20 de diciembre de 2020). Introducción a la criptografía moderna. CRC Press. p. 262. ISBN 978-1-351-13302-9.
4. Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media, Inc., pág. 1085. ISBN 978-1-57955-008-0.
5. "Técnicas de pruebas estadísticas para la generación pseudoaleatoria".
6. Razborov, Alexander; Rudich, Steven (agosto de 1997). "Pruebas naturales". Revista de Ciencias de la Computación y de Sistemas . 55 (1): 24–35. doi : 10.1006/jcss.1997.1494 .

• Sanjeev Arora y Boaz Barak, Complejidad computacional: un enfoque moderno, Cambridge University Press (2009), ISBN 9780521424264 . 
• Oded Goldreich , Complejidad computacional: una perspectiva conceptual , Cambridge University Press (2008), ISBN 978-0-521-88473-0 . 
• Oded Goldreich , Fundamentos de criptografía: herramientas básicas , Cambridge University Press (2001), ISBN 9780521791724 . 
• Naor, Joseph; Naor, Moni (1990), "Espacios de probabilidad de sesgo pequeño: construcciones y aplicaciones eficientes", Actas del vigésimo segundo simposio anual de la ACM sobre teoría de la computación - STOC '90, págs. 213-223, CiteSeerX  10.1.1.421.2784 , doi :10.1145/100216.100244, ISBN 978-0897913614, Número de identificación del sujeto  14031194{{citation}}: Mantenimiento CS1: fecha y año ( enlace )
• Viola, Emanuele (2008). "La suma de d generadores de sesgo pequeño engaña a polinomios de grado D". 2008 23.ª Conferencia anual IEEE sobre complejidad computacional (PDF) . pp. 124–127. CiteSeerX  10.1.1.220.1554 . doi :10.1109/CCC.2008.16. ISBN. 978-0-7695-3169-4.
• Este artículo incorpora material del generador pseudoaleatorio de PlanetMath , que se encuentra bajo la licencia Creative Commons Attribution/Share-Alike License .