Argumento híbrido (criptografía)

En criptografía , el argumento híbrido es una técnica de prueba utilizada para demostrar que dos distribuciones son computacionalmente indistinguibles .

Los argumentos híbridos tuvieron su origen en los artículos de Andrew Yao en 1982 y de Shafi Goldwasser y Silvio Micali en 1983. ^[1]

Formalmente, para mostrar que dos distribuciones D ₁ y D ₂ son computacionalmente indistinguibles, podemos definir una secuencia de distribuciones híbridas D ₁  := H ₀ , H ₁ , ..., H _t =: D ₂ donde t es polinomial en el parámetro de seguridad n . Defina la ventaja de cualquier algoritmo probabilístico eficiente (tiempo limitado por polinomios) A como

${\displaystyle {\mathsf {Adv}}_{H_{i},H_{i+1}}^{\mathsf {dist}}(\mathbf {A} ):=\left|\Pr[x{\stackrel {\$}{\gets }}H_{i}:\mathbf {A} (x)=1]-\Pr[x{\stackrel {\$}{\gets }}H_{i+1}:\mathbf {A} (x)=1]\right|,}$

donde el símbolo de dólar ($) indica que tomamos una muestra de un elemento de la distribución al azar.

Por la desigualdad triangular , queda claro que para cualquier algoritmo de tiempo polinomial probabilístico A ,

${\displaystyle {\mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )\leq \sum _{i=0}^{t -1}{\mathsf {Adv}}_{H_{i},H_{i+1}}^{\mathsf {dist}}(\mathbf {A}).}$

Por lo tanto, debe existir algún k st 0 ≤ k < t(n) y

${\displaystyle {\mathsf {Adv}}_{H_{k},H_{k+1}}^{\mathsf {dist}}(\mathbf {A} )\geq {\mathsf {Adv}}_{ D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )/t(n).}$

Dado que t está acotado polinomialmente, para cualquier algoritmo A , si podemos demostrar que tiene una función de ventaja despreciable entre las distribuciones H _i y H _{i +1} para cada i , es decir,

${\displaystyle \epsilon (n)\geq {\mathsf {Adv}}_{H_{k},H_{k+1}}^{\mathsf {dist}}(\mathbf {A} )\geq {\ mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )/t(n),}$

De ello se deduce inmediatamente que su ventaja para distinguir las distribuciones D ₁ = H ₀ y D ₂ = H _t también debe ser despreciable. Este hecho da lugar al argumento híbrido: basta con encontrar dicha secuencia de distribuciones híbridas y demostrar que cada par de ellas es computacionalmente indistinguible. ^[2]

El argumento híbrido se utiliza ampliamente en criptografía. Algunas pruebas sencillas que utilizan argumentos híbridos son:

• Si no se puede predecir eficientemente el siguiente bit de la salida de algún generador de números, entonces este generador es un generador de números pseudoaleatorios (PRG). ^[3]
• Podemos expandir de forma segura un PRG con salida de 1 bit a un PRG con salida de n bits. ^[4]

• Sistema de prueba interactivo
• Componibilidad universal

• Dodis, Yevgeniy. "Introducción a la criptografía, notas de la lección 5" (PDF) . Archivado desde el original (PDF) el 25 de diciembre de 2014.
• Pass, Rafael. "Un curso de criptografía" (PDF) .
• Fischlin, Marc; Mittelbach, Arno. "Una descripción general del argumento híbrido" (PDF) .