El aprendizaje con errores ( LWE ) es el problema computacional de inferir una-función sobre un anillo finito de muestras dadas algunos de los cuales pueden ser erróneos. Se supone que el problema LWE es difícil de resolver [1] y, por tanto, útil en criptografía .
Más precisamente, el problema LWE se define como sigue. Dejardenotar el anillo de números enteros módulo y deja denotar el conjunto de - vectores sobre. Existe una cierta función lineal desconocida, y la entrada al problema LWE es una muestra de pares , dónde y , de modo que con alta probabilidad . Además, la desviación de la igualdad está de acuerdo con algún modelo de ruido conocido. El problema exige encontrar la función, o alguna aproximación cercana al mismo, con alta probabilidad.
El problema LWE fue introducido por Oded Regev en 2005 [2] (quien ganó el Premio Gödel 2018 por este trabajo), es una generalización del problema del aprendizaje por paridad . Regev mostró que el problema de LWE es tan difícil de resolver como varios problemas de celosía del peor de los casos . Posteriormente, el problema LWE se ha utilizado como un supuesto de dureza para crear criptosistemas de clave pública , [2] [3] como el aprendizaje de anillo con intercambio de claves de errores por Peikert. [4]
Definición
Denotamos por el grupo aditivo en reales módulo uno . Dejarser un vector fijo. Dejar ser una distribución de probabilidad fija sobre . Denotamos por la distribución en obtenido de la siguiente manera.
- Elige un vector de la distribución uniforme sobre ,
- Elige un número de la distribución ,
- Evaluar , dónde es el producto interior estándar en , la división se hace en el campo de los reales (o más formalmente, esta "división por"es una notación para el homomorfismo de grupo cartografía a ), y la adición final está en .
- Salida del par .
El problema del aprendizaje con errores es encontrar , dado acceso a polinomialmente muchas muestras de elección de .
Para cada , denotamos por el gaussiano unidimensional con media cero y varianza, es decir, la función de densidad es dónde , y deja ser la distribución en obtenido al considerar módulo uno. La versión de LWE considerada en la mayoría de los resultados sería
Versión de decisión
El problema de LWE descrito anteriormente es la versión de búsqueda del problema. En la versión de decisión ( DLWE ), el objetivo es distinguir entre productos internos ruidosos y muestras uniformemente aleatorias de(prácticamente, alguna versión discretizada). Regev [2] mostró que las versiones de decisión y búsqueda son equivalentes cuando es un primo acotado por algún polinomio en .
Resolución de decisión asumiendo la búsqueda
Intuitivamente, si tenemos un procedimiento para el problema de búsqueda, la versión de decisión se puede resolver fácilmente: simplemente alimente las muestras de entrada para el problema de decisión al solucionador del problema de búsqueda. Denote las muestras dadas por. Si el solucionador devuelve un candidato, para todos , calcular . Si las muestras son de una distribución LWE, los resultados de este cálculo se distribuirán de acuerdo con, pero si las muestras son uniformemente aleatorias, estas cantidades también se distribuirán uniformemente.
Resolviendo la búsqueda asumiendo una decisión
Para la otra dirección, dado un solucionador para el problema de decisión, la versión de búsqueda se puede resolver de la siguiente manera: Recuperar una coordenada a la vez. Para obtener la primera coordenada,, adivina y haga lo siguiente. Elige un númerouniformemente al azar. Transforma las muestras dadascomo sigue. Calcular. Envíe las muestras transformadas al solucionador de decisiones.
Si la suposición era correcto, la transformación toma la distribución consigo mismo, y de lo contrario, ya que es primo, lo lleva a la distribución uniforme. Entonces, dado un solucionador de tiempo polinomial para el problema de decisión que yerra con una probabilidad muy pequeña, ya que está limitado por algún polinomio en , solo se necesita tiempo polinomial para adivinar todos los valores posibles para y use el solucionador para ver cuál es el correcto.
Después de obtener , seguimos un procedimiento análogo para cada una de las otras coordenadas . Es decir, transformamos nuestro muestras de la misma manera, y transformar nuestra muestras calculando , donde el está en el coordinar. [2]
Peikert [3] demostró que esta reducción, con una pequeña modificación, funciona para cualquier que es un producto de distintos, pequeños (polinomios en ) primos. La idea principal es si, para cada , adivina y comprueba si es congruente con , y luego use el teorema del resto chino para recuperar.
Dureza media de la caja
Regev [2] mostró el azar auto-reducibilidad de los LWE y DLWE problemas para arbitraria y . Muestras dadas de , Es fácil ver eso son muestras de .
Entonces, supongamos que hubiera un conjunto tal que , y para distribuciones , con , DLWE fue fácil.
Entonces habría algún distintivo , quien, dadas las muestras , podría decir si eran uniformemente aleatorios o de . Si necesitamos distinguir muestras uniformemente aleatorias de, dónde se elige uniformemente al azar de , simplemente podríamos probar diferentes valores muestreados uniformemente al azar de , calcular y alimentar estas muestras a . Desde comprende una gran fracción de , con alta probabilidad, si elegimos un número polinomial de valores para , encontraremos uno tal que , y distinguirá con éxito las muestras.
Por lo tanto, no hay tal puede existir, lo que significa que LWE y DLWE son (hasta un factor polinomial) tan difíciles en el caso promedio como en el peor de los casos.
Resultados de dureza
Resultado de Regev
Para una celosía n- dimensional, deje el parámetro de suavizado denotar el más pequeño tal que dónde es el dual de y se extiende a conjuntos sumando los valores de función en cada elemento del conjunto. Dejar denotar la distribución gaussiana discreta en de ancho para una celosía y real . La probabilidad de cada es proporcional a .
El problema de muestreo discreto de Gauss (DGS) se define de la siguiente manera: Una instancia de es dado por un -rejilla dimensional y un numero . El objetivo es generar una muestra de. Regev muestra que hay una reducción de a para cualquier función .
Regev luego muestra que existe un algoritmo cuántico eficiente para dado acceso a un oráculo para para entero y tal que . Esto implica la dureza de LWE. Aunque la prueba de esta afirmación funciona para cualquier, para crear un criptosistema, el tiene que ser polinomio en .
El resultado de Peikert
Peikert demuestra [3] que hay una reducción de tiempo polinomial probabilística de la problema en el peor de los casos para resolver utilizando muestras para parámetros , , y .
Uso en criptografía
El problema LWE sirve como un problema versátil utilizado en la construcción de varios criptosistemas [2] [3] [5] [6] . En 2005, Regev [2] mostró que la versión de decisión de LWE es difícil asumiendo la dureza cuántica de los problemas de celosía (por como arriba) y con ). En 2009, Peikert [3] demostró un resultado similar asumiendo solo la dureza clásica del problema relacionado.. La desventaja del resultado de Peikert es que se basa en una versión no estándar de un problema más fácil (en comparación con SIVP), GapSVP.
Criptosistema de clave pública
Regev [2] propuso un criptosistema de clave pública basado en la dureza del problema LWE . El criptosistema, así como la prueba de seguridad y corrección, son completamente clásicos. El sistema se caracteriza por y una distribución de probabilidad en . La configuración de los parámetros utilizados en las pruebas de corrección y seguridad es
- , generalmente un número primo entre y .
- para una constante arbitraria
- por , dónde es una distribución de probabilidad obtenida al muestrear una variable normal con media y variación estándar y reduciendo el resultado modulo .
El criptosistema se define entonces por:
- Clave privada : la clave privada es una elegido uniformemente al azar.
- Clave pública : Elija vectores uniforme e independientemente. Elija compensaciones de error independientemente de acuerdo con . La clave pública consta de
- Cifrado : el cifrado de un bit se hace eligiendo un subconjunto aleatorio de y luego definiendo como
- Descifrado : el descifrado de es Si está más cerca de que a , y de lo contrario.
La prueba de la corrección se deriva de la elección de parámetros y algún análisis de probabilidad. La prueba de seguridad se reduce a la versión de decisión de LWE : un algoritmo para distinguir entre cifrados (con los parámetros anteriores) de y se puede utilizar para distinguir entre y la distribución uniforme sobre
Criptosistema seguro CCA
Peikert [3] propuso un sistema que es seguro incluso contra cualquier ataque de texto cifrado elegido .
Intercambio de llaves
La idea de utilizar LWE y Ring LWE para el intercambio de claves fue propuesta y archivada en la Universidad de Cincinnati en 2011 por Jintai Ding. La idea proviene de la asociatividad de las multiplicaciones de matrices y los errores se utilizan para proporcionar la seguridad. El documento [7] apareció en 2012 después de que se presentara una solicitud de patente provisional en 2012.
La seguridad del protocolo está probada en base a la dureza de resolver el problema LWE. En 2014, Peikert presentó un esquema de transporte de claves [8] siguiendo la misma idea básica de Ding, donde también se utiliza la nueva idea de enviar una señal adicional de 1 bit para redondear en la construcción de Ding. La implementación de la "nueva esperanza" [9] seleccionada para el experimento post-cuántico de Google, [10] utiliza el esquema de Peikert con variación en la distribución de errores.
Ver también
Referencias
- ^ Regev, Oded (2009). "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía". Revista de la ACM . 56 (6): 1–40. doi : 10.1145 / 1568318.1568324 . S2CID 207156623 .
- ^ a b c d e f g h Oded Regev, "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía", en Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la computación (Baltimore, MD, EE. UU.: ACM , 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603 .
- ^ a b c d e f Chris Peikert, "Criptosistemas de clave pública del problema del vector más corto en el peor de los casos: resumen extendido", en Actas del 41 ° simposio anual de ACM sobre teoría de la computación (Bethesda, MD, EE. UU.: ACM, 2009 ), 333–342, http://portal.acm.org/citation.cfm?id=1536414.1536461 .
- ^ Peikert, Chris (1 de octubre de 2014). "Criptografía de celosía para Internet". En Mosca, Michele (ed.). Criptografía post-cuántica . Apuntes de conferencias en informática. 8772 . Springer International Publishing. págs. 197–219. CiteSeerX 10.1.1.800.4743 . doi : 10.1007 / 978-3-319-11659-4_12 . ISBN 978-3-319-11658-7.
- ^ Chris Peikert y Brent Waters, "Funciones de trampilla con pérdida y sus aplicaciones", en Actas del 40º simposio anual de ACM sobre teoría de la computación (Victoria, Columbia Británica, Canadá: ACM, 2008), 187-196, http: // portal .acm.org / citation.cfm? id = 1374406 .
- ^ Craig Gentry, Chris Peikert y Vinod Vaikuntanathan, "Trampas para celosías duras y nuevas construcciones criptográficas", en Actas del 40 ° simposio anual de ACM sobre teoría de la computación (Victoria, Columbia Británica, Canadá: ACM, 2008), 197-206 , http://portal.acm.org/citation.cfm?id=1374407 .
- ^ Lin, Jintai Ding, Xiang Xie, Xiaodong (1 de enero de 2012). "Un esquema de intercambio de claves seguro y demostrable basado en el problema de aprendizaje con errores" . Cite journal requiere
|journal=
( ayuda ) - ^ Peikert, Chris (1 de enero de 2014). "Criptografía de celosía para Internet" . Cite journal requiere
|journal=
( ayuda ) - ^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (1 de enero de 2015). "Intercambio de claves post-cuántica - una nueva esperanza" . Cite journal requiere
|journal=
( ayuda ) - ^ "Experimentar con criptografía post-cuántica" . Blog de seguridad en línea de Google . Consultado el 8 de febrero de 2017 .