Aprender con errores (firmados)

$\underline{\bf Background}$

En 2005, Regev [1] introdujo el problema de Aprendizaje con errores (LWE), una generalización del problema de Paridad de aprendizaje con error. La suposición de la dureza de este problema para ciertas opciones de parámetros ahora subyace a las pruebas de seguridad para una gran cantidad de criptosistemas post-cuánticos en el campo de la criptografía basada en la red. Las versiones "canónicas" de LWE se describen a continuación.

Preliminares:

Sea el grupo aditivo de reales módulo 1, es decir, tomando valores en . Para enteros positivos y , un vector "secreto" , una distribución de probabilidad on , deje sea ​​la distribución en obtenida eligiendo uniformemente en aleatorio, dibujando un término de error y generando$\mathbb{T} = \mathbb{R}/\mathbb{Z}$$[0, 1)$$n$$2 \le q \le poly(n)$${\bf s} \in \mathbb{Z}_q^n$$\phi$$\mathbb{R}$$A_{{\bf s}, \phi}$$\mathbb{Z}_q^n \times \mathbb{T}$${\bf a} \in \mathbb{Z}_q^n$$x \leftarrow \phi$$({\bf a}, b' = \langle{\bf a}, s\rangle/q + x) \in \mathbb{Z}_q^n \times \mathbb{T}$.

Sea la "discretización" de . Es decir, primero extraemos una muestra de y luego la salida . Aquí denota el redondeo al valor integral más cercano, para que podamos ver como . A s , ϕ ( a , b ′ ) A s , ϕ ( a , b ) = ( a , ⌊ b ′ ⋅ q ⌉ ) ∈ Z n q × Z q ⌊ ∘ ⌉ ∘ ( a , b ) ( un , b = ⟨ una , es$A_{{\bf s}, \overline{\phi}}$$A_{{\bf s}, \phi}$$({\bf a}, b')$$A_{{\bf s}, \phi}$$({\bf a}, b) = ({\bf a}, \lfloor b'\cdot q\rceil) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$$\lfloor\circ\rceil$$\circ$$({\bf a}, b)$$({\bf a}, b= \langle {\bf a}, {\bf s} \rangle + \lfloor q\cdot x\rceil)$

En la configuración canónica, consideramos que la distribución de errores es gaussiana. Para cualquier , la función de densidad de una distribución de probabilidad gaussiana unidimensional sobre viene dada por . Escribimos como abreviatura para la discretización deα > 0 R D α ( x ) = e - π ( x / α ) 2 / α A s , α A s , D $\phi$$\alpha > 0$$\mathbb{R}$$D_{\alpha}(x)=e^{-\pi(x/\alpha)^2}/\alpha$$A_{{\bf s}, \alpha}$$A_{{\bf s}, D_\alpha}$

Definición de LWE:

En la versión de búsqueda nos dan muestras de , que podemos ver como ecuaciones lineales "ruidosas" (Nota: ): N = p o l y ( n ) A s , α a i , s ∈ Z n q , b i ∈ Z$LWE_{n, q, \alpha}$$N = poly(n)$$A_{{\bf s}, \alpha}$${\bf a}_i, {\bf s} \in \mathbb{Z}_q^n, b_i \in \mathbb{Z}_q$

⋮ ⟨ un N , s ⟩ ≈ chi b

donde el error en cada ecuación se extrae independientemente de un gaussiano discreto (centrado) de ancho . Nuestro objetivo es recuperar . (Observe que, sin error, podemos resolver esto con la eliminación gaussiana, pero en presencia de este error, la eliminación gaussiana falla dramáticamente).$\alpha q$${\bf s}$

En la versión de decisión , se nos da acceso a un oráculo que devuelve muestras cuando se consulta. Se nos promete que todas las muestras provienen de o de la distribución uniforme . Nuestro objetivo es distinguir cuál es el caso.O s ( a , b ) A s , α U ( Z n q ) × U ( Z q$DLWE_{n, q, \alpha}$$\mathcal{O}_{\bf s}$$({\bf a}, b)$$A_{{\bf s}, \alpha}$$U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)$

Se cree que ambos problemas son cuando .α q > 2 $hard$$\alpha q > 2\sqrt n$

Conexión a la teoría de la complejidad:

Se sabe (ver [1], [2] para más detalles) que LWE corresponde a resolver un problema de Decodificación de distancia limitada (BDD) en la red dual de una instancia de GapSVP. Un algoritmo de tiempo polinomial para LWE implicaría un algoritmo de tiempo polinómico para aproximar ciertos problemas de red tales como SIVP y SVP dentro de donde es un factor polinomial pequeño (digamos, ).1/αn$\tilde O(n/\alpha)$$1/\alpha$$n^2$

Límites Algorítmicos Actuales

Cuando para estrictamente menos de 1/2, Arora y Ge [3] dan un algoritmo de tiempo subexponencial para LWE. La idea es que, a partir de propiedades bien conocidas del gaussiano, dibujar términos de error tan pequeños se ajuste a una configuración de "ruido estructurado", excepto con una probabilidad exponencialmente baja. Intuitivamente en esta configuración, cada vez que hubiéramos recibido 1 muestra, recibimos un bloque de muestras con la promesa de que no más de una fracción constante contiene error. Usan esta observación para "linealizar" el problema y enumeran el espacio de error. ϵ $\alpha q \le n^\epsilon$$\epsilon$$m$

$\underline{\bf Question}$

Supongamos, en cambio, que tenemos acceso a un oráculo . Cuando se le consulta, primeras consultas para obtener una muestra . Si se extrajo de , entonces devuelve una muestra donde representa la "dirección" (o -valor "signo") del término de error . Si se dibujó al azar, entonces devuelve O + s O s ( a ,b)( a ,b) A s , α O + s ( a ,b,d)∈ Z n q × Z q × Z 2 d±( a ,b) O + s ( a ,b,d)←$\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}$$({\bf a}, b)$$({\bf a}, b)$$A_{{\bf s}, \alpha}$$\mathcal{O}_{\bf s}^+$$({\bf a}, b, d) \in \mathbb{Z}_q^n \times \mathbb{Z}_q \times \mathbb{Z}_2$$d$$\pm$$({\bf a}, b)$$\mathcal{O}_{\bf s}^+$d $({\bf a}, b, d) \leftarrow U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)\times U(\mathbb{Z}_2)$ . (Alternativamente, podríamos considerar el caso cuando el bit se elige de forma contradictoria cuando se dibuja de manera uniforme al azar).$d$$b$

Sea como antes, excepto que ahora para una constante suficientemente grande , digamos. (Esto es para garantizar que el error absoluto en cada ecuación no se vea afectado). Defina los problemas de Aprendizaje con error firmado (LWSE) y como antes, excepto que ahora tenemos el consejo adicional para el signo de cada término de error.α q > c $n, q, \alpha$ cLWSE n , q , α DLWSE n , q , $\alpha q > c\sqrt n$$c$$LWSE_{n, q, \alpha}$$DLWSE_{n, q, \alpha}$

¿Alguna versión de LWSE es significativamente más fácil que sus contrapartes de LWE?

P.ej

1. ¿Existe un algoritmo de tiempo subexponencial para LWSE?

2. ¿Qué pasa con un algoritmo de tiempo polinómico basado en, digamos, programación lineal?

Además de la discusión anterior, mi motivación es un interés en explorar opciones algorítmicas para LWE (de las cuales actualmente tenemos relativamente pocas para elegir). En particular, la única restricción conocida para proporcionar buenos algoritmos para el problema está relacionada con la magnitud de los términos de error. Aquí, la magnitud sigue siendo la misma, pero el rango de error en cada ecuación ahora es "monótono" de cierta manera. (Un comentario final: no estoy al tanto de esta formulación del problema que aparece en la literatura; parece ser original).

Referencias

[1] Regev, Oded. "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía", en JACM 2009 (originalmente en STOC 2005) ( PDF )

[2] Regev, Oded. "El problema del aprendizaje con errores", encuesta invitada en CCC 2010 ( PDF )

[3] Arora, Sanjeev y Ge, Rong. "Nuevos algoritmos para aprender en presencia de errores", en ICALP 2011 ( PDF )

(¡Guau! Después de tres años de pasar, ahora es fácil de responder. ¡Qué gracioso cómo va eso! - Daniel)

Este problema de "Aprendizaje con errores (firmados)" ( LWSE ), tal como lo inventé y dije anteriormente (hace tres años), reduce trivialmente el problema de Aprendizaje extendido con errores ( eLWE ) introducido por primera vez en el trabajo Público bi-deniable -Cifrado clave por O'Neill, Peikert y Waters en CRYPTO 2011.

El problema de eLWE se define de manera análoga a la LWE "estándar" (es decir, [ Regev2005 ]), excepto que el distintivo (eficiente) de las distribuciones recibe además "pistas" en el vector de error de la muestra LWE , en forma de ( posiblemente ruidosos) productos internos con un vector arbitrario . (En las aplicaciones, es a menudo el vector de clave de descifrado de algún sistema criptográfico).→ z → $\vec{x}$$\vec{z}$$\vec{z}$

Formalmente, el problema se describe a continuación:$\mathsf{eLWE}_{n,m,q,\chi,\beta}$

Para un número entero , y una distribución de error sobre , el problema del aprendizaje extendido con errores es distinguir entre los siguientes pares de distribuciones: donde y , y donde$q = q(n) \ge 2$$\chi = \chi(n)$$\mathbb{Z}_q$

Es fácil ver que eLWE captura "el espíritu" de LWSE , aunque se puede mostrar una reducción formal sin demasiado esfuerzo adicional.

Las principales ideas de seguimiento para comprender el problema Extended-LWE se desarrollan en los trabajos:

• Seguridad circular y KDM para el cifrado basado en la identidad de Alperin-Sheriff y Peikert
• Dureza clásica del aprendizaje con errores de Brakerski, Langlois, Peikert, Regev y Stehle

Dependiendo de si su clave secreta vive en o es binaria (y la naturaleza de varias otras opciones de parámetros), puede usar las reducciones del primer o segundo papel para finalmente reducir cuántica / clásica de con factor de aproximación a LWSE .G a p S V P α α≥Ω( n 1.5$\mathbb{Z}_q$$\mathsf{GapSVP}_\alpha$$\alpha \ge \Omega(n^{1.5})$