Cómo construir funciones aleatorias

Se desarrolla una teoría constructiva de la aleatoriedad para funciones, basada en la complejidad computacional, y se presenta un generador de funciones seudoaleatorias. Este generador es un algoritmo determinista de tiempo polinómico que transforma pares (g, r), donde g es cualquier función unidireccional y r es una cadena aleatoria de k bits, en funciones computables en tiempo polinómico ƒ r: 1, …, 2 k → 1, …, 2 k. Estas ƒ r no pueden ser distinguidas de funciones aleatorias por ningún algoritmo probabilístico de tiempo polinómico que pregunte y reciba el valor de una función en argumentos de su elección. El resultado tiene aplicaciones en criptografía, construcciones aleatorias y teoría de la complejidad.