En criptografía y teoría de la computación , la prueba de Yao es una prueba definida por Andrew Chi-Chih Yao en 1982, [1] contra secuencias pseudoaleatorias. Una secuencia de palabras pasa la prueba de Yao si un atacante con un poder computacional razonable no puede distinguirla de una secuencia generada uniformemente al azar.
Declaración formal
Circuitos booleanos
Dejar ser un polinomio, y ser una colección de conjuntos de -bits de secuencias largas, y para cada , dejar ser una distribución de probabilidad en, y ser un polinomio. Una colección de prediccioneses una colección de circuitos booleanos de tamaño menor que. Dejar sea la probabilidad de que en la entrada , una cadena seleccionada al azar en con probabilidad , , es decir
Además, deja ser la probabilidad de que en la entrada a -bit secuencia larga seleccionada uniformemente al azar en. Nosotros decimos eso pasa la prueba de Yao si para toda la colección de predicciones , para todos menos para un número finito , para todo polinomio :
Formulación probabilística
Como en el caso de la prueba del siguiente bit , la colección de predicción utilizada en la definición anterior puede ser reemplazada por una máquina de Turing probabilística, que trabaja en tiempo polinomial. Esto también produce una definición estrictamente más sólida de la prueba de Yao (ver el teorema de Adleman ). De hecho, se podrían decidir propiedades indecidibles de la secuencia pseudoaleatoria con los circuitos no uniformes descritos anteriormente, mientras que las máquinas BPP siempre pueden ser simuladas por máquinas de Turing deterministas en tiempo exponencial .
Referencias
- ^ Andrew Chi-Chih Yao . Teoría y aplicaciones de las funciones de trampilla . En Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.