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 distinguir entre ellas, excepto con una probabilidad insignificante.

Definicion formal

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 de tiempo polinómico probabilístico no uniforme A , la siguiente cantidad es una función insignificante 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 todo 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 simplemente adivinara. ${\displaystyle D_{n}\approx E_{n}}$ ${\displaystyle n\to \infty }$

Nociones relacionadas

Implícita en la definición está la condición de que el algoritmo debe decidir 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 pueden distinguirse mediante algoritmos de tiempo polinomial que analizan múltiples muestras se consideran indistinguibles mediante muestreo de tiempo polinomial . ^{[2] : 107} Si el algoritmo de tiempo polinómico puede generar muestras en tiempo polinómico, o tiene acceso a un oráculo aleatorio que genera muestras para él, entonces la indistinguibilidad mediante muestreo de tiempo polinómico es equivalente a la indistinguibilidad computacional. ^{[2] : 108} ${\displaystyle A}$

Referencias

1. Conferencia 4: Indistinguibilidad computacional, generadores pseudoaleatorios
2. 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, Silvio Micali y Phillip Rogaway , The Round Complexity of Secure Protocols (resumen ampliado), 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 computacionalmente indistinguible en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .