Resumen Técnico: Hacia la dureza en el peor de los casos para LPN de bajo ruido

Declaración del Problema

El problema de Aprendizaje con Paridad y Ruido (LPN, por sus siglas en inglés) es un supuesto fundamental en la criptografía, sirviendo como base para primitivas de clave simétrica y cifrado de clave pública (PKE). Mientras que la dureza en el caso promedio del análogo problema de Aprendizaje con Errores (LWE) está respaldada por supuestos de redes (lattices) en el peor de los casos, establecer una reducción similar de caso peor a caso promedio para LPN sigue siendo una cuestión abierta central.

Las reducciones existentes para LPN, específicamente las de Brakerski et al. [BLVW19] y Yu y Zhang [YZ21], dependen del suavizado estadístico de códigos lineales. Estos métodos requieren que las combinaciones dispersas aleatorias de las filas de una matriz generadora sean estadísticamente cercanas a la distribución uniforme. Este requisito limita inherentemente la dureza de caso promedio resultante a tasas de ruido tan altas como $1/2 - 1/\text{poly}(n)$. Tales tasas de ruido elevadas son insuficientes para aplicaciones de clave pública, que típicamente requieren dureza con tasas de ruido inversamente polinómicas (por ejemplo, $n^{-1/2}$) o tasas de ruido constantes contra algoritmos de tiempo subexponencial. Además, los supuestos del peor de los casos requeridos por estas reducciones existentes (por ejemplo, la dureza del Problema del Vecino más Cercano con tasas de ruido muy bajas) son o bien débiles o requieren supuestos de preprocesamiento poco realistas.

Metodología

Los autores proponen un nuevo enfoque que relaja el requisito de suavizado estadístico hacia la indistinguibilidad computacional. En lugar de exigir que las combinaciones dispersas aleatorias de las filas del código sean estadísticamente cercanas a la uniforme, los autores solo requieren que sean computacionalmente indistinguibles de la uniforme.

Este cambio conduce a una estructura de "ganar-ganar" basada en las propiedades de una matriz dada $A \in \mathbb{F}_2^{m \times n}$:

1. Decodificación del Código: Si las combinaciones aleatorias son computacionalmente indistinguibles de la uniforme, se puede utilizar un resolvedor eficiente de LPN para decodificar el código generado por $A$ a partir de ruido aleatorio.
2. Distinción del Dual: Si las combinaciones aleatorias no son computacionalmente indistinguibles de la uniforme, el distinguidor resuelve efectivamente una versión de decisión del problema de decodificación del código dual de $A$ (específicamente, distinguir síndromes de peso fijo de la distribución uniforme).

La reducción se basa en la observación de que si $A$ se ve como una matriz generadora, entonces $A^T$ actúa como la matriz de comprobación de paridad del código dual. Recuperar un vector $r$ dado $r^T A$ es equivalente a decodificar el código dual con $r$ como el vector de ruido.

Contribuciones Clave y Resultados

1. Teorema de Reducción Principal

El artículo presenta una reducción (Teorema 3.1) que muestra que la dureza de LPN puede derivarse de la dureza simultánea en el peor de los casos de dos problemas:

• Decodificar un código generado por una matriz $A$ a partir de ruido aleatorio.
• Distinguir códigos ruidosos (síndromes) del código dual de $A$ de la distribución uniforme.

Teorema 1.1 (Informal): Suponga que existe un algoritmo eficiente con ventaja no despreciable en resolver Search LPN con $n$ variables, $t$ muestras y tasa de ruido $n^{-\alpha}$ (para una constante $\alpha < 1$). Entonces, para cualquier constante $\beta > 0$ tal que $\alpha + \beta < 1$, existen algoritmos eficientes $S$ y $D$ tales que para cualquier matriz $A$:

• O bien $S$ puede decodificar el código generado por $A$ a partir de ruido aleatorio de tasa $n^{-(\alpha+\beta)}$.
• O bien $D$ puede distinguir códigos ruidosos del dual de $A$ de la distribución uniforme para una tasa de ruido $n^{\beta}/m$.

2. Instanciación para Criptografía de Clave Pública

Al establecer parámetros específicos, los autores demuestran que su reducción produce dureza de LPN en el régimen requerido para la construcción de cifrado de clave pública de Alekhnovich [Ale03].

• Parámetros: Estableciendo $\alpha = 0.5$ (tasa de ruido objetivo $n^{-0.5}$), $\beta = 0.45$, y $m = O(n^{2.9})$.
• Resultado: Esto implica la dureza de LPN con $t=2n$ muestras y tasa de ruido $n^{-0.5}$, asumiendo la dureza simultánea en el peor de los casos de la decodificación de un código y su dual.
• Significancia: Este régimen de parámetros era previamente inaccesible mediante reducciones de caso peor utilizando suavizado estadístico.

3. Desafíos Técnicos y Soluciones

Los autores abordan la dificultad de pasar de un suavizado estadístico a uno computacional. En el entorno estadístico, el análisis de Fourier maneja fácilmente la distribución conjunta de la matriz suavizada y el ruido. En el entorno computacional, los autores muestran que incluso si $r^T A$ es pseudialeatorio, la fuga $r^T e$ podría potencialmente hacer que la distribución conjunta sea distinguible.

• Solución: La reducción construye un algoritmo $S$ que decodifica a partir de ruido de Bernoulli aleatorio en lugar de ruido de peor caso. Los autores prueban que para la mayoría de las elecciones de los vectores de suavizado $r$, los bits $r^T e$ se comportan como variables de Bernoulli independientes incluso tras fijar $r$. Esto permite que la reducción proceda sin requerir que $r^T e$ sea insesgado para todos los vectores de error del peor de los casos, una condición que anteriormente era una barrera.

Significancia y Reivindicaciones

El artículo afirma proporcionar un camino para establecer la dureza de caso promedio de LPN con tasas de ruido inversamente polinómicas (específicamente $n^{-1/2}$) basadas en supuestos del peor de los casos. Este es un paso significativo hacia la construcción de cifrado de clave pública desde supuestos de dureza en el peor de los casos, un objetivo que ha sido esquivo para LPN en comparación con LWE.

Los autores señalan explícitamente las siguientes limitaciones y reivindicaciones modestas:

• Supuesto No Estándar: La reducción depende de la dureza simultánea de la decodificación de un código y su dual. Este supuesto es no estándar y no ha sido estudiado independientemente. Los autores no afirman que este supuesto sea más débil que los existentes, sino que es una condición necesaria para su enfoque específico para sortear la barrera del suavizado estadístico.
• Ruido Aleatorio vs. de Peor Caso: El decodificador resultante $S$ funciona contra ruido de Bernoulli aleatorio, mientras que las reducciones previas (por ejemplo, [BLVW19]) producían decodificadores para ruido de peso limitado del peor de los casos. Los autores reconocen que extender su enfoque al ruido del peor de los casos fortalecería significativamente el resultado, pero requeriría nuevas herramientas para razonar sobre la entropía computacional.
• Tiempo Subexponencial: Los mejores algoritmos conocidos para los problemas del peor de los casos especificados en el teorema (decodificación de un código genérico y su dual) corren en tiempo subexponencial. Por lo tanto, la reducción establece la dureza de LPN contra algoritmos de tiempo polinómico basándose en supuestos de dureza en el peor de los casos de tiempo subexponencial.

En resumen, el artículo ofrece una reducción de "ganar-ganar limpia" que intercambia el requisito estadístico de suavizado por uno computacional, permitiendo la dureza de LPN a tasas de ruido suficientes para el cifrado de clave pública, siempre que se acepte la dureza simultánea de la decodificación de un código y su dual.