Indistinguibilidad computacional

En informática, relación entre dos familias de distribuciones.

En complejidad computacional y criptografía , dos familias de distribuciones son computacionalmente indistinguibles si ningún algoritmo eficiente puede determinar la diferencia entre ellas excepto con una probabilidad insignificante.

Definición formal

Sean y dos conjuntos de distribuciones indexados por un parámetro de seguridad n (que usualmente 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 : ${\displaystyle \scriptstyle \{D_{n}\}_{n\in \mathbb {N} }}$ ${\displaystyle \scriptstyle \{E_{n}\}_{n\in \mathbb {N} }}$

${\displaystyle \delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|.}$

denotado . ^[1] En otras palabras, el comportamiento de cada algoritmo eficiente A no cambia significativamente cuando se dan muestras según 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 simplemente adivinara. ${\displaystyle D_{n}\approx E_{n}}$ ${\displaystyle n\to \infty }$

Nociones relacionadas

En la definición está implícita la condición de que el algoritmo, , debe tomar una decisión basándose en una única muestra de una de las distribuciones. Se podría concebir una situación en la que el algoritmo que intenta 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 un 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 mediante un muestreo en tiempo polinomial es equivalente a la indistinguibilidad computacional. ^{[2] : 108} ${\displaystyle A}$

Referencias

1. Lección 4 - Indistinguibilidad computacional, generadores pseudoaleatorios
2. Goldreich, O. (2003). Fundamentos de 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 (Resumen ampliado), 1990, págs. 503–513
• Shafi Goldwasser y Silvio Micali . Encriptación probabilística. JCSS, 28(2):270–299, 1984
• Oded Goldreich . Fundamentos de criptografía: Volumen 2 – Aplicaciones básicas. Cambridge University Press, 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 se encuentra bajo la licencia Creative Commons Attribution/Share-Alike License .