Indistinguibilidad computacional

En complejidad computacional y criptografía , dos familias de distribuciones son computacionalmente indistinguibles si ningún algoritmo eficiente puede diferenciarlas excepto con una pequeña probabilidad.

Sean y 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 A de tiempo polinomial probabilístico no uniforme , la siguiente cantidad es una función despreciable en n : $\scriptstyle \{D_{n}\}_{n\in \mathbb {N} }$ $\scriptstyle \{E_{n}\}_{n\in \mathbb {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. $D_{n}\aprox. E_{n}$ $n\to \infty$

Implícita en la definición está la condición de que el algoritmo, debe decidir en base a una sola muestra de una de las distribuciones. Se podría concebir una situación en la que el algoritmo que trata de distinguir entre dos distribuciones pudiera acceder a tantas muestras como necesitara. Por lo tanto, dos conjuntos que no se pueden distinguir mediante algoritmos de tiempo polinomial que analizan múltiples muestras se consideran indistinguibles mediante muestreo en 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 en tiempo polinomial es equivalente a la indistinguibilidad computacional. ^[2]^{: 108} ${\ estilo de visualización A}$

Este artículo incorpora material computacionalmente indistinguible en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .