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 en la clase puede distinguir entre la salida del generador y la distribución uniforme. La semilla aleatoria en sí misma 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 dado. 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 del circuito (no comprobados) 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 dado se basa en supuestos de dureza actualmente no comprobados.
Definición
Dejar ser una clase de funciones. Estas funciones son las pruebas estadísticas que el generador pseudoaleatorio intentará engañar, y generalmente son algoritmos . A veces, las pruebas estadísticas también se denominan adversarios o diferenciadores . [1]
Una función con es un generador pseudoaleatorio contracon sesgo si, por cada en , la distancia estadística entre las distribuciones y es como máximo , dónde es la distribución uniforme en.
La cantidad se llama la longitud de la semilla y la cantidadse llama el tramo del generador pseudoaleatorio.
Un generador pseudoaleatorio contra una familia de adversarios con sesgo es una familia de generadores pseudoaleatorios , dónde es un generador pseudoaleatorio contra con sesgo y longitud de la semilla .
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 pequeña longitud de semilla y sesgo, y tal que la salida del generador pueda calcularse mediante el mismo tipo de algoritmo.
En criptografía
En criptografía , la clasegeneralmente consta de todos los circuitos de tamaño polinomial en la entrada y con un solo bit de salida, y uno está interesado en diseñar generadores pseudoaleatorios que sean computables mediante un algoritmo de tiempo polinomial y cuyo sesgo sea insignificante en el tamaño del circuito. Estos generadores pseudoaleatorios a veces se denominan generadores pseudoaleatorios criptográficamente seguros (CSPRG) .
No se sabe si existen generadores pseudoaleatorios criptográficamente seguros. Demostrar que existen es difícil, ya que su existencia implica P ≠ NP , que se cree ampliamente, pero es un problema famoso y abierto. La existencia de generadores pseudoaleatorios criptográficamente seguros también se cree ampliamente [ cita requerida ] y 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 pads de un solo uso . Es bien sabido que para cifrar un mensaje m de manera que el texto cifrado no proporcione información sobre el texto plano, 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 la clave se puede reducir significativamente usando un generador pseudoaleatorio si la seguridad perfecta es reemplazada por la seguridad semántica . Las construcciones comunes de cifrados de flujo se basan en generadores pseudoaleatorios.
Los generadores pseudoaleatorios también se pueden utilizar para construir criptosistemas de clave simétrica , donde una gran cantidad de mensajes se pueden cifrar de forma segura bajo la misma clave. Tal construcción puede basarse en una familia de funciones pseudoaleatorias , que generaliza la noción de un 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 la década de 1980, se había desarrollado evidencia de que algunos generadores comunes daban resultados incorrectos en casos tales como propiedades de transición de fase del modelo 3D Ising y formas de agregados de difusión limitada. Luego, en la década de 1990, se utilizaron varias idealizaciones de simulaciones físicas, basadas en recorridos aleatorios , funciones de correlación , localización de estados propios, etc., como pruebas de generadores pseudoaleatorios. [2]
Pruebas
NIST anunció pruebas de aleatoriedad SP800-22 para probar 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 estadística basada en la distancia LILtest. [3]
Para la desaleatorización
Una aplicación principal de los generadores pseudoaleatorios radica en la desaleatorización de la computación que se basa en la aleatoriedad, sin corromper el resultado de la computación. Las computadoras físicas son máquinas deterministas y obtener una verdadera aleatoriedad puede ser un desafío. Los generadores pseudoaleatorios se pueden utilizar para simular eficientemente algoritmos aleatorios con 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 "computable de manera eficiente" contra 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 al algoritmo aleatorizado 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.
Construcciones
Por tiempo polinomial
Una cuestión fundamental en la teoría de la complejidad computacional es si todos los algoritmos aleatorios en tiempo polinómico para problemas de decisión pueden simularse determinísticamente en tiempo polinomial. La existencia de una simulación tal implicaría que BPP = P . Para realizar tal simulación, es suficiente construir generadores pseudoaleatorios contra la familia F de todos los circuitos de tamaño s ( n ) cuyas entradas tienen una longitud n y emiten un solo bit, donde s ( n ) es un polinomio arbitrario, la longitud de la 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 asumiendo que existe un problema de decisión que se puede calcular en el tiempo 2 O ( n ) en entradas de longitud n pero requiere circuitos de tamaño 2 Ω ( n ) .
Para 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 necesitemos confiar en esas suposiciones no probadas. Una clase para la que se ha hecho esto es la clase de máquinas cuyo espacio de trabajo está delimitado por. Usando un truco de cuadratura repetido conocido como teorema de Savitch , es fácil demostrar que cada cálculo probabilístico de espacio logarítmico puede simularse en el espacio.. Noam Nisan (1992) mostró que esta desaleatorización en realidad se puede lograr con un generador pseudoaleatorio de longitud de semilla que engaña a todos -máquinas espaciales. El generador de Nisan ha sido utilizado por Saks y Zhou (1999) para mostrar que el cálculo probabilístico del espacio logarítmico se puede simular de forma determinista en el espacio.. Este resultado sigue siendo el resultado de desaleatorización más conocido para las máquinas de espacio de registro general en 2012.
Para funciones lineales
Cuando las pruebas estadísticas consisten en todas las funciones lineales multivariadas sobre algún campo finito , se habla de generadores con polarización épsilon . La construcción de Naor y Naor (1990) logra una longitud de semilla de, que es óptimo hasta factores constantes. Los generadores pseudoaleatorios para funciones lineales a menudo sirven como un bloque de construcción para generadores pseudoaleatorios más complicados.
Para polinomios
Viola (2008) demuestra que tomando la suma de generadores de sesgo pequeño engañan a los polinomios de grado . La longitud de la semilla es.
Para circuitos de profundidad constante
Circuitos de profundidad constante que producen un solo bit de salida. [ cita requerida ]
Limitaciones de probabilidad
No se ha demostrado que existan los generadores pseudoaleatorios utilizados en criptografía y desaleatorización algorítmica universal, aunque se cree ampliamente [ 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 probar en el marco de pruebas naturales asumiendo la existencia de variantes más fuertes de generadores pseudoaleatorios criptográficos [ cita requerida ] .
Referencias
- ↑ Katz, Jonathan (6 de noviembre de 2014). Introducción a la criptografía moderna . Lindell, Yehuda (Segunda ed.). Boca Ratón. ISBN 9781466570269. OCLC 893721520 .
- ^ Wolfram, Stephen (2002). Un nuevo tipo de ciencia . Wolfram Media, Inc. pág. 1085 . ISBN 978-1-57955-008-0.
- ^ "Técnicas de prueba estadística para generación pseudoaleatoria" .
- Sanjeev Arora y Boaz Barak, Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 9780521424264 .
- Oded Goldreich , Computational Complexity: A Conceptual Perspective , Cambridge University Press (2008), ISBN 978-0-521-88473-0 .
- Oded Goldreich , Fundamentos de la criptografía: herramientas básicas , Cambridge University Press (2001), ISBN 9780521791724 .
- Naor, José; Naor, Moni (1990), "Espacios de probabilidad de sesgo pequeño: construcciones y aplicaciones eficientes" , Actas del 22º Simposio anual de ACM sobre teoría de la computación, STOC 1990 : 213–223, CiteSeerX 10.1.1.421.2784 , doi : 10.1145 / 100216.100244 , ISBN 978-0897913614, S2CID 14031194
- Viola, Emanuele (2008), "La suma de d generadores de sesgo pequeño engaña a los polinomios de grado d" (PDF) , Actas de la 23ª Conferencia Anual sobre Complejidad Computacional (CCC 2008) : 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 en PlanetMath , que está bajo la licencia Creative Commons Attribution / Share-Alike License .