stringtranslate.com

Aprendiendo con errores

En criptografía , el aprendizaje con errores ( LWE ) es un problema matemático que se utiliza ampliamente para crear algoritmos de cifrado seguros . [1] Se basa en la idea de representar la información secreta como un conjunto de ecuaciones con errores. En otras palabras, LWE es una forma de ocultar el valor de un secreto introduciéndole ruido. [2] En términos más técnicos, se refiere al problema computacional de inferir una función lineal -aria sobre un anillo finito a partir de muestras dadas, algunas de las cuales pueden ser erróneas. Se conjetura 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 de la siguiente manera. Denotemos el anillo de números enteros módulo y denotemos el conjunto de vectores sobre . Existe una determinada función lineal desconocida , y la entrada al problema LWE es una muestra de pares , donde y , de modo que con alta probabilidad . Además, la desviación de la igualdad se produce según algún modelo de ruido conocido. El problema requiere encontrar la función , o alguna aproximación cercana a la misma, con alta probabilidad.

El problema LWE fue introducido por Oded Regev en 2005 [3] (quien ganó el Premio Gödel 2018 por este trabajo); es una generalización del problema de aprendizaje de paridad . Regev demostró que el problema LWE es tan difícil de resolver como varios problemas reticulares del peor de los casos . Posteriormente, el problema LWE se ha utilizado como supuesto de dureza para crear criptosistemas de clave pública , [3] [4] como el aprendizaje en anillo con intercambio de claves con errores de Peikert. [5]

Definición

Denotado por el grupo aditivo en reales módulo uno . Sea un vector fijo. Sea una distribución de probabilidad fija sobre . Denotemos por la distribución obtenida de la siguiente manera.

  1. Elija un vector de la distribución uniforme sobre ,
  2. Elija un número de la distribución ,
  3. Evalúe dónde está el producto interno estándar en , la división se realiza en el campo de reales (o más formalmente, esta "división por " es una notación para el mapeo de homomorfismo de grupo en ), y la suma final está en .
  4. Salida del par .

El problema del aprendizaje con errores consiste en encontrar , dado acceso polinómico, a muchas muestras de elección .

Para cada , denotemos por el gaussiano unidimensional con media y varianza cero , es decir, la función de densidad es donde , y sea la distribución obtenida considerando 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 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 (prácticamente, alguna versión discretizada del mismo). Regev [3] demostró que las versiones de decisión y búsqueda son equivalentes cuando es un primo acotado por algún polinomio en .

Decisión de resolución asumiendo 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 introduzca las muestras de entrada para el problema de decisión al solucionador del problema de búsqueda. Denota las muestras dadas por . Si el solucionador devuelve un candidato , para todos , calcule . Si las muestras provienen de una distribución LWE, los resultados de este cálculo se distribuirán según , pero si las muestras son uniformemente aleatorias, estas cantidades también se distribuirán uniformemente.

Resolver búsqueda asumiendo 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, adivine y haga lo siguiente. Elija un número uniformemente al azar. Transforme las muestras dadas de la siguiente manera. Calcular . Envíe las muestras transformadas al solucionador de decisiones.

Si la suposición fue correcta, la transformación lleva la distribución a sí misma, y ​​en caso contrario, como es prima, la lleva a la distribución uniforme. Entonces, dado un solucionador de tiempo polinomial para el problema de decisión que se equivoca 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 y usar el solucionador para ver cuál es el correcto.

Una vez obtenidas , seguimos un procedimiento análogo para cada otra coordenada . Es decir, transformamos nuestras muestras de la misma manera y las transformamos calculando , donde está en la coordenada. [3]

Peikert [4] demostró que esta reducción, con una pequeña modificación, funciona para cualquier producto de números primos distintos y pequeños (polinomiales en ). La idea principal es si , para cada uno , adivina y verifica si es congruente y luego usa el teorema chino del resto para recuperar .

Dureza promedio

Regev [3] mostró la autorreducibilidad aleatoria de los problemas LWE y DLWE para arbitrarios y . Dadas muestras de , es fácil ver que son muestras de .

Entonces, supongamos que hubiera algún conjunto tal que , y para las distribuciones , con DLWE fuera fácil.

Entonces habría algún distinguidor que, dadas las muestras , podría decir si son uniformemente aleatorias o de . Si necesitamos distinguir muestras uniformemente aleatorias de dónde se elige uniformemente al azar , podríamos simplemente probar diferentes valores muestreados uniformemente al azar , calcular y alimentar estas muestras . Dado que comprende una gran fracción de , con alta probabilidad, si elegimos un número polinómico de valores para , encontraremos uno tal que y distinguiremos con éxito las muestras.

Por lo tanto, tal cosa no puede existir, lo que significa que LWE y DLWE son (hasta un factor polinómico) tan difíciles en el caso promedio como lo son en el peor de los casos.

Resultados de dureza

El resultado de Regev.

Para una red de n dimensiones , sea el parámetro de suavizado el más pequeño, tal que donde sea el dual de y se extienda a conjuntos sumando los valores de función en cada elemento del conjunto. Denotemos la distribución gaussiana discreta de ancho para una red y real . La probabilidad de cada uno es proporcional a .

El problema de muestreo gaussiano discreto (DGS) se define de la siguiente manera: una instancia de está dada por una red dimensional y un número . 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 el acceso dado a un oráculo para números enteros y tales que . Esto implica la dureza para LWE. Aunque la prueba de esta afirmación funciona para cualquier , para crear un criptosistema, el módulo tiene que ser polinomio en .

El resultado de Peikert

Peikert demuestra [4] que existe una reducción de tiempo polinomial probabilística desde el problema en el peor de los casos hasta la resolución utilizando muestras para los parámetros , y .

Uso en criptografía

El problema LWE sirve como un problema versátil utilizado en la construcción de varios criptosistemas [3] [4] [6] [7] . En 2005, Regev [3] demostró que la versión de decisión de LWE es difícil asumiendo la dureza cuántica de los problemas de la red (como arriba) y con ). En 2009, Peikert [4] demostró un resultado similar asumiendo sólo 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 sencillo (en comparación con SIVP), GapSVP.

Criptosistema de clave pública

Regev [3] 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

El criptosistema queda entonces definido por:

La prueba de corrección se desprende de la elección de los parámetros y de algún análisis de probabilidad. La prueba de seguridad es por reducción 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 [4] 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 presentada en la Universidad de Cincinnati en 2011 por Jintai Ding. La idea surge de la asociatividad de las multiplicaciones de matrices y los errores se utilizan para proporcionar seguridad. El artículo [8] 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 dificultad de resolver el problema LWE. En 2014, Peikert presentó un esquema de transporte de claves [9] 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 "nueva esperanza" [10] seleccionada para el experimento post-cuántico de Google, [11] utiliza el esquema de Peikert con variación en la distribución del error.

Aprendizaje en anillo con firma de errores (RLWE-SIG)

Artículo principal: Aprendizaje en anillo con firma de errores.

Lyubashevsky creó y convirtió en una firma digital en 2011 una versión RLWE del clásico protocolo de identificación Feige-Fiat-Shamir . Los detalles de esta firma fueron ampliados en 2012 por Gunesyu, Lyubashevsky y Popplemann en 2012 y publicados en su artículo "Practical Lattice Based Cryptography - A Signature Scheme for Embedded Systems". Estos artículos sentaron las bases para una variedad de algoritmos de firma recientes, algunos basados ​​directamente en el problema del aprendizaje en anillo con errores y otros que no están vinculados a los mismos problemas difíciles de RLWE.

Ver también

Referencias

  1. ^ ab Regev, Oded (2009). "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía". Revista de la ACM . 56 (6): 1–40. arXiv : 2401.03703 . doi :10.1145/1568318.1568324. S2CID  207156623.
  2. ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (noviembre de 2013). "Sobre redes ideales y aprendizaje con errores sobre anillos". Revista de la ACM . 60 (6): 1–35. doi :10.1145/2535925. ISSN  0004-5411. S2CID  1606347.
  3. ^ abcdefgh Oded Regev, “Sobre redes, 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 informática (Baltimore, MD, EE. UU.: ACM, 2005), 84–93 , http://portal.acm.org/citation.cfm?id=1060590.1060603.
  4. ^ abcdef Chris Peikert, "Criptosistemas de clave pública del problema del vector más corto en el peor de los casos: resumen ampliado", en Actas del 41.º simposio anual de ACM sobre teoría de la informática (Bethesda, MD, EE. UU.: ACM, 2009), 333–342 , http://portal.acm.org/citation.cfm?id=1536414.1536461.
  5. ^ Peikert, Chris (1 de octubre de 2014). "Criptografía de celosía para Internet". En Mosca, Michele (ed.). Criptografía poscuántica . Apuntes de conferencias sobre informática. vol. 8772. Publicación internacional Springer. 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. S2CID  8123895.
  6. ^ Chris Peikert y Brent Waters, “Lossy trapdoor funciones y sus aplicaciones”, en Actas del 40.º simposio anual de ACM sobre teoría de la informática (Victoria, Columbia Británica, Canadá: ACM, 2008), 187-196, http://portal .acm.org/citation.cfm?id=1374406.
  7. ^ Craig Gentry, Chris Peikert y Vinod Vaikuntanathan, "Trampillas para celosías duras y nuevas construcciones criptográficas", en Actas del 40º simposio anual de ACM sobre teoría de la informática (Victoria, Columbia Británica, Canadá: ACM, 2008), 197-206 , http://portal.acm.org/citation.cfm?id=1374407.
  8. ^ Lin, Jintai Ding, Xiang Xie, Xiaodong (1 de enero de 2012). "Un esquema de intercambio de claves simple y demostrablemente seguro basado en el problema del aprendizaje con errores". Archivo ePrint de criptología .{{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. ^ Peikert, Chris (1 de enero de 2014). "Criptografía de celosía para Internet". Archivo ePrint de criptología .
  10. ^ Alkim, Erdem; Ducas, Leo; Pöppelmann, Thomas; Schwabe, Peter (1 de enero de 2015). "Intercambio de claves poscuántico: una nueva esperanza". Archivo ePrint de criptología .
  11. ^ "Experimentar con criptografía poscuántica". Blog de seguridad en línea de Google . Consultado el 8 de febrero de 2017 .