Public Key Encryption from High-Corruption Constraint Satisfaction Problems

1. Introducción y Problema

El objetivo central de este trabajo es construir un esquema de Cifrado de Clave Pública (PKE) basado en nuevas fuentes de dureza computacional, específicamente en Problemas de Satisfacción de Restricciones (CSP) con una tasa de corrupción extremadamente alta ($1 - o(1)$).

• Contexto: La criptografía actual depende principalmente de problemas de teoría de números (factores, logaritmos discretos), que son vulnerables a computadoras cuánticas, o de problemas de retículos/códigos. Existe una necesidad urgente de encontrar suposiciones de dureza alternativas y robustas ("win-win": si se rompe, se avanza en la comprensión matemática; si no, se tiene seguridad).
• El Problema: La mayoría de los esquemas PKE basados en CSPs existentes (como los de Applebaum, Barak y Wigderson) solo logran seguridad cuasi-polinomial ($\lambda^{O(\log \lambda)}$). Esto se debe a una barrera de fuerza bruta: el descifrado requiere adivinar la ubicación de un componente oculto de tamaño logarítmico, lo que un adversario puede hacer en tiempo cuasi-polinomial.
• La Propuesta: Los autores proponen un esquema que logra una seguridad cuasi-exponencial ($\exp(2^{\log^{\Omega(1)} \lambda})$), acercándose a la seguridad sub-exponencial, evitando la necesidad de algoritmos de descifrado de fuerza bruta.

2. Metodología y Suposiciones de Dureza

El esquema se basa en la intractabilidad de dos problemas CSP específicos bajo un régimen de alta corrupción (donde la mayoría de las restricciones son reemplazadas por valores aleatorios):

A. LARP-CSP (Large Alphabet Random Predicate CSP)

• Definición: Un CSP sobre un grafo de factores (hipergrafo) que es fuertemente expansor. Las variables tienen un alfabeto grande ($\Sigma$).
• Corrupción: Se elige una asignación oculta $s$. Para cada restricción, con probabilidad $1 - o(1)$, el valor de salida se reemplaza por un elemento aleatorio del alfabeto de salida $\Gamma$. Con probabilidad $o(1)$, se mantiene el valor calculado por una función aleatoria $f_i$ aplicada a $s$.
• Conjetura: Distinguir entre un conjunto de restricciones aleatorias y un conjunto con una asignación "plantada" (aunque altamente corrupta) es computacionalmente intratable para algoritmos de tamaño polinomial en el tamaño del alfabeto.
• Innovación: A diferencia de los generadores pseudoaleatorios de Goldreich (que usan alfabetos binarios y sin corrupción), LARP-CSP introduce entropía masiva a través de funciones aleatorias de gran alfabeto y alta corrupción, lo que dificulta ataques que explotan la estructura del grafo.

B. kXOR de Alta Corrupción

• Definición: El problema estándar de kXOR (suma par de $k$ variables) sobre un grafo de factores aleatorio.
• Corrupción: Similar a LARP-CSP, la mayoría de las ecuaciones de paridad se reemplazan por bits aleatorios ($1 - o(1)$).
• Diferencia clave: La tasa de corrupción es $1 - o(1)$ en lugar de una constante pequeña o inversamente polinomial, lo que hace que el problema sea mucho más difícil de atacar con algoritmos locales o lineales.

3. Contribuciones Clave y Técnicas

A. Nueva Técnica de "Plantado de Trampas" (Trapdoors)

El núcleo del trabajo es un método novedoso para plantar una "trampa" criptográfica utilizando el grafo de factores extendido por etiquetas (label extended factor graph).

• Mecanismo:
  1. Se genera una matriz expansora $G$ (código de corrección de errores).
  2. Se utiliza un CSP de alta corrupción (LARP-CSP) para generar la clave pública. La clave pública es esencialmente una matriz $H$ que lista todas las preimágenes locales de las funciones del CSP.
  3. La clave secreta es un mapeo $\zeta$ que identifica qué filas de la matriz pública $H$ corresponden a una versión "punteada" (con algunas filas borradas) de la matriz original $G$.
  4. Esto permite que el descifrador extraiga un subvector del cifrado que corresponde a un código de corrección de errores ruidoso, el cual puede ser decodificado eficientemente.

B. Construcción de Códigos de Corrección de Errores

Los autores presentan la primera construcción uniforme de un código de corrección de errores con matriz generadora de baja densidad y expansora que permite la decodificación eficiente desde una fracción de corrupción de $1 - o(1)$.

• Base Teórica: Utilizan códigos de Reed-Muller de baja tasa.
• Algoritmo: Proporcionan un algoritmo explícito para muestrear una matriz generadora expansora (mejorando trabajos anteriores de Oliveira, Santhanam y Tell que solo probaban la existencia no constructiva).
• Decodificación: Utilizan un algoritmo de Saptharishi, Shpilka y Volk para distinguir entre vectores aleatorios ruidosos y palabras de código ruidosas, incluso con tasas de error cercanas al 100%.

C. Seguridad Cuasi-Exponencial

Al evitar la necesidad de adivinar la ubicación de la trampa (que en esquemas anteriores requería fuerza bruta sobre un espacio logarítmico), el esquema logra una seguridad significativamente mayor. La seguridad se reduce a la dificultad de romper los CSPs de alta corrupción, lo que se traduce en una seguridad de orden $\exp(2^{\log^{\Omega(1)} \lambda})$.

4. Resultados y Evidencia de Dureza

Los autores no solo proponen el esquema, sino que proporcionan pruebas de seguridad contra una amplia gama de ataques conocidos para respaldar sus conjeturas:

1. Ataques de Incrustación de Baja Complejidad: Demuestran que los ataques de Oliveira, Santhanam y Tell (que rompen PRGs de Goldreich en grafos expansores específicos) no funcionan contra LARP-CSP debido a la entropía masiva de las funciones aleatorias. Se prueba un límite inferior que descarta cualquier ataque de este tipo, incluso si el adversario elige el grafo y la estructura de prueba después de ver las funciones.
2. Algoritmos de Polinomios de Bajo Grado: Se demuestra que los algoritmos basados en polinomios de grado hasta $n^{0.99}$ no pueden distinguir las distribuciones. Esto implica que algoritmos combinatorios de tiempo $\exp(n^{0.99})$ son ineficaces.
3. Refutaciones de Cálculo Polinomial: Se establecen límites inferiores para el sistema de prueba de cálculo polinomial, mostrando que cualquier refutación requiere un tamaño de al menos $\exp(n^{0.99})$.
4. kXOR: Se citan resultados existentes que muestran que el kXOR con alta corrupción engaña a algoritmos locales, pruebas de suma de cuadrados (SoS) y algoritmos de paso de mensajes aproximados.

5. Significado e Impacto

• Avance en Fundamentos Criptográficos: Este trabajo ofrece una ruta viable hacia la PKE post-cuántica basada en suposiciones de CSPs, diversificando las bases de la criptografía más allá de la teoría de números y los retículos.
• Superación de Barreras de Seguridad: Es el primer esquema PKE basado en CSPs de alta corrupción que logra seguridad cuasi-exponencial, superando la barrera cuasi-polinomial de trabajos anteriores.
• Interacción entre Complejidad y Criptografía: El trabajo conecta profundamente la teoría de la complejidad promedio (CSPs, grafos expansores) con la construcción de primitivas criptográficas, sugiriendo que la "dureza promedio" de problemas NP puede ser suficiente para la criptografía de clave pública.
• Perspectiva "Win-Win": Si las conjeturas de dureza se rompen, se obtiene un entendimiento profundo de los límites de los algoritmos para CSPs. Si no se rompen, se obtiene un sistema de cifrado seguro y eficiente.

En resumen, Hair y Sahai han diseñado un marco criptográfico innovador que explota la dificultad de resolver problemas de satisfacción de restricciones cuando la señal es extremadamente débil (alta corrupción), utilizando una ingeniería de códigos de corrección de errores y grafos expansores para crear una trampa de descifrado eficiente y segura.