En complejidad computacional y criptografía , dos familias de distribuciones son indistinguibles computacionalmente si ningún algoritmo eficiente puede diferenciar entre ellas excepto con una pequeña probabilidad.
Definicion formal
Dejar y ser dos conjuntos de distribución indexados por un parámetro de seguridad n (que generalmente se refiere a la longitud de la entrada); decimos que son computacionalmente indistinguibles si para cualquier algoritmo de tiempo polinomial probabilístico no uniforme A , la siguiente cantidad es una función despreciable en n :
denotado . [1] En otras palabras, el comportamiento de cada algoritmo eficiente A no cambia significativamente cuando se le dan muestras de acuerdo con D n o E n en el límite como. Otra interpretación de la indistinguibilidad computacional es que los algoritmos de tiempo polinomial que intentan activamente distinguir entre los dos conjuntos no pueden hacerlo: que cualquier algoritmo de este tipo solo funcionará insignificantemente mejor que si uno solo tuviera que adivinar.
Nociones relacionadas
Implícita en la definición está la condición de que el algoritmo, , debe decidir basándose en una sola muestra de una de las distribuciones. Se podría concebir una situación en la que el algoritmo que intenta distinguir entre dos distribuciones pueda acceder a tantas muestras como necesite. Por lo tanto, dos conjuntos que no se pueden distinguir mediante algoritmos de tiempo polinomial que miran múltiples muestras se consideran indistinguibles por muestreo de tiempo polinomial . [2] : 107 Si el algoritmo de tiempo polinomial puede generar muestras en tiempo polinomial, o tiene acceso a un oráculo aleatorio que genera muestras para él, entonces la indistinguibilidad por muestreo de tiempo polinomial es equivalente a la indistinguibilidad computacional. [2] : 108
Referencias
- ^ Clase 4 - Indistinguibilidad computacional, generadores pseudoaleatorios
- ↑ a b Goldreich, O. (2003). Fundamentos de la criptografía. Cambridge, Reino Unido: Cambridge University Press.
enlaces externos
- Yehuda Lindell . Introducción a la criptografía
- Donald Beaver y Silvio Micali y Phillip Rogaway , The Round Complexity of Secure Protocols (Extended Abstract), 1990, págs. 503–513
- Shafi Goldwasser y Silvio Micali . Cifrado probabilístico. JCSS, 28 (2): 270–299, 1984
- Oded Goldreich . Fundamentos de la criptografía: Volumen 2 - Aplicaciones básicas. Prensa de la Universidad de Cambridge, 2004.
- Jonathan Katz , Yehuda Lindell , "Introducción a la criptografía moderna: principios y protocolos", Chapman & Hall / CRC, 2007
Este artículo incorpora material de computacionalmente indistinguible en PlanetMath , que está bajo la licencia Creative Commons Attribution / Share-Alike License .