Generador pseudoaleatorio

---

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 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 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 probado) 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 suposiciones de dureza actualmente no probadas.

Sea una clase de funciones. Estas funciones son las pruebas estadísticas que el generador pseudoaleatorio intentará engañar, y suelen ser algoritmos . En ocasiones, las pruebas estadísticas también se denominan adversarios o distintivos . ^[1]${\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}}$${\ estilo de visualización \ ell <n}$${\displaystyle {\mathcal {A}}}$ ${\ estilo de visualización \ épsilon}$${\ estilo de visualización A}$${\displaystyle {\mathcal {A}}}$${\displaystyle A(G(U_{\ell }))}$${\ estilo de visualización A (U_ {n})}$${\ estilo de visualización \ épsilon}$${\displaystyle U_{k}}$${\displaystyle \{0,1\}^{k}}$

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

---