Aprendizaje de anillos con intercambio de claves de errores

En criptografía , un algoritmo de intercambio de clave pública es un algoritmo criptográfico que permite a dos partes crear y compartir una clave secreta, que pueden usar para cifrar mensajes entre ellas. El intercambio de claves de aprendizaje en anillo con errores ( RLWE-KEX ) es uno de una nueva clase de algoritmos de intercambio de clave pública que están diseñados para ser seguros contra un adversario que posee una computadora cuántica . Esto es importante porque algunos algoritmos de clave pública en uso hoy en día serán fácilmente descifrados por una computadora cuántica si se implementan dichas computadoras. RLWE -KEX es uno de un conjunto de algoritmos criptográficos postcuánticos que se basan en la dificultad de resolver ciertos problemas matemáticos que involucran retículos . A diferencia de los algoritmos criptográficos más antiguos basados ​​en retículos, el RLWE -KEX es demostrablemente reducible a un problema difícil conocido en retículos.

Fondo

Desde la década de 1980, la seguridad de los intercambios de claves criptográficas y firmas digitales a través de Internet se ha basado principalmente en un pequeño número de algoritmos de clave pública . La seguridad de estos algoritmos se basa en un número igualmente pequeño de problemas computacionales difíciles en la computación clásica. Estos problemas son la dificultad de factorizar el producto de dos números primos cuidadosamente elegidos , la dificultad de calcular logaritmos discretos en un cuerpo finito cuidadosamente elegido y la dificultad de calcular logaritmos discretos en un grupo de curvas elípticas cuidadosamente elegido . Estos problemas son muy difíciles de resolver en una computadora clásica (el tipo de computadora que el mundo ha conocido desde la década de 1940 hasta hoy) pero se resuelven con bastante facilidad con una computadora cuántica relativamente pequeña que use solo entre 5 y 10 mil bits de memoria. Existe optimismo en la industria informática de que las computadoras cuánticas de mayor escala estarán disponibles alrededor de 2030. Si se construyera una computadora cuántica de tamaño suficiente, todos los algoritmos de clave pública basados ​​en estos tres problemas clásicos difíciles serían inseguros. Esta criptografía de clave pública se utiliza hoy en día para proteger sitios web de Internet, proteger la información de inicio de sesión de las computadoras y evitar que nuestras computadoras acepten software malicioso.

La criptografía que no es susceptible a ataques por parte de una computadora cuántica se conoce como criptografía cuántica segura o criptografía postcuántica . Una clase de algoritmos criptográficos resistentes a la cuántica se basa en un concepto llamado " aprendizaje con errores " introducido por Oded Regev en 2005. ^[1] Una forma especializada de aprendizaje con errores opera dentro del anillo de polinomios sobre un campo finito . Esta forma especializada se llama aprendizaje en anillo con errores o RLWE .

Existen diversos algoritmos criptográficos que funcionan con el paradigma RLWE. Además del algoritmo de intercambio de claves de clave pública que se presenta en este artículo, existen algoritmos de cifrado de clave pública , algoritmos de cifrado homomórfico y algoritmos de firma digital RLWE.

Un algoritmo de intercambio de claves es un tipo de algoritmo de clave pública que establece una clave secreta compartida entre dos comunicantes en un enlace de comunicaciones. El ejemplo clásico de un intercambio de claves es el intercambio de claves Diffie-Hellman . El intercambio consiste en una transmisión desde un extremo de la línea y una transmisión desde el otro extremo del enlace. Diffie-Hellman y Diffie-Hellman de curva elíptica son los dos algoritmos de intercambio de claves más populares.

El intercambio de claves RLWE está diseñado para ser un reemplazo " cuántico seguro " para los intercambios de claves Diffie-Hellman y Diffie-Hellman de curva elíptica ampliamente utilizados que se utilizan para asegurar el establecimiento de claves secretas en canales de comunicación no confiables. Al igual que Diffie-Hellman y Diffie-Hellman de curva elíptica, el intercambio de claves Ring-LWE proporciona una propiedad criptográfica llamada " secreto de reenvío "; cuyo objetivo es reducir la efectividad de los programas de vigilancia masiva y garantizar que no haya claves secretas a largo plazo que puedan verse comprometidas y permitir el descifrado masivo.

Introducción

A partir de un entero primo q, el intercambio de claves Ring-LWE funciona en el anillo de polinomios módulo un polinomio con coeficientes en el cuerpo de enteros mod q (es decir, el anillo ). La multiplicación y la suma de polinomios funcionarán de la manera habitual con resultados de una multiplicación reducida mod . ${\displaystyle \Phi (x)}$ ${\displaystyle R_{q}:=Z_{q}[x]/\Phi (x)}$ ${\displaystyle \Phi (x)}$

La idea de utilizar LWE y Ring LWE para el intercambio de claves fue propuesta y presentada por primera vez 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 ^[2] apareció en 2012 después de que se presentara una solicitud de patente provisional en 2012. La seguridad del protocolo está demostrada en función de la dificultad de resolver el problema LWE.

En 2014, Peikert presentó un esquema de transporte de clave ^[3] 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 el redondeo en la construcción de Ding.

La implementación de "Nueva Esperanza" ^[4] seleccionada para el experimento post-cuántico de Google, ^[5] utiliza el esquema de Peikert con variación en la distribución del error.

Para un poco más de 128 bits de seguridad , Singh presenta un conjunto de parámetros que tienen claves públicas de 6956 bits para el esquema de Peikert. ^[6] La clave privada correspondiente sería de aproximadamente 14.000 bits. Una versión RLWE de la variante MQV clásica de un intercambio de claves Diffie-Hellman fue publicada más tarde por Zhang et al. en 2014. La seguridad de ambos intercambios de claves está directamente relacionada con el problema de encontrar vectores cortos aproximados en una red ideal. Este artículo seguirá de cerca el trabajo RLWE de Ding en "Un esquema de intercambio de claves simple y demostrablemente seguro basado en el problema del aprendizaje con errores". ^[2] Para esta presentación, un polinomio típico se expresa como:

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}$

Los coeficientes de este polinomio son números enteros módulo  q . El polinomio será el polinomio ciclotómico . Cuando n es una potencia de 2 entonces ^{[6] [7]} ${\displaystyle a_{i}}$ ${\displaystyle \Phi (x)}$ ${\displaystyle \Phi (x)=x^{n}+1.}$

El algoritmo RLWE-KEX utiliza polinomios que se consideran "pequeños" con respecto a una medida llamada " norma de infinito ". La norma de infinito para un polinomio es simplemente el valor del coeficiente más grande del polinomio cuando los coeficientes se consideran como números enteros en Z en lugar de (es decir, del conjunto {−( q  − 1)/2,..., 0, ... ( q  − 1)/2}). La seguridad del algoritmo depende de la capacidad de generar polinomios aleatorios que sean pequeños con respecto a la norma de infinito. Esto se hace simplemente generando aleatoriamente los coeficientes para un polinomio (s _n-1 , ..., s ₀ ) que se garantiza que sean pequeños o que es muy probable que lo sean. Hay dos formas comunes de hacer esto: ${\displaystyle Zq}$

1. Usando Muestreo Uniforme – Los coeficientes del polinomio pequeño son muestreados uniformemente de un conjunto de coeficientes pequeños. Sea b un entero que es mucho menor que q . Si elegimos aleatoriamente coeficientes del conjunto: { − b , −b + 1, −b + 2. ... −2, −1, 0, 1, 2, ... , b  − 2, b  − 1, b } el polinomio será pequeño con respecto al límite (b). Singh sugiere usar b = 5. ^[6] Por lo tanto, los coeficientes se elegirían del conjunto { q  − 5, q  − 4, q  − 3, q  ​​− 2, q  − 1, 0, 1, 2, 3, 4, 5 }.
2. Uso de muestreo gaussiano discreto : para un valor impar de q, los coeficientes se eligen aleatoriamente mediante un muestreo del conjunto { −(q − 1)/2 a ( q  − 1)/2 } según una distribución gaussiana discreta con media 0 y parámetro de distribución  σ . Las referencias describen con todo detalle cómo se puede lograr esto. Es más complicado que el muestreo uniforme, pero permite una prueba de seguridad del algoritmo. Se puede encontrar una descripción general del muestreo gaussiano en una presentación de Peikert. ^[8]

En el resto de este artículo, los polinomios pequeños aleatorios se muestrearán de acuerdo con una distribución que se especifica simplemente como D . Además, q será un primo impar tal que q sea congruente con 1 mod 4 y 1 mod 2n. Otros casos para q y n se analizan en profundidad en "A Toolkit for Ring-LWE Cryptography" y en "Even More Practical Key Exchange for the Internet using Lattice Cryptography" de Singh ^{[9] [10]} y otro artículo de Singh. Un polinomio público fijo, a(x), compartido por todos los usuarios de la red. Se genera de forma determinista a partir de una fuente criptográficamente segura.

Dado a ( x ) como se indica, podemos elegir aleatoriamente los polinomios pequeños s ( x ) y e ( x ) para que sean la "clave privada" en un intercambio de claves públicas. La clave pública correspondiente será el polinomio p ( x ) = a ( x ) s ( x ) + 2 e ( x ).

El intercambio de claves

El intercambio de claves se llevará a cabo entre dos dispositivos. Habrá un iniciador para el intercambio de claves designado como (I) y un respondedor designado como (R). Tanto I como R conocen q , n , a ( x ), y tienen la capacidad de generar pequeños polinomios de acuerdo con la distribución con parámetro . La distribución es generalmente la distribución gaussiana discreta en el anillo . La descripción que sigue no contiene ninguna explicación de por qué el intercambio de claves da como resultado la misma clave en ambos extremos de un enlace. Más bien, especifica sucintamente los pasos a seguir. Para una comprensión completa de por qué el intercambio de claves da como resultado que el iniciador y el respondedor tengan la misma clave, el lector debe consultar el trabajo de referencia de Ding et al. ^[2] ${\displaystyle \chi _{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \chi _{\alpha }}$ ${\displaystyle R_{q}=Z_{q}[x]/\Phi (x)}$

El intercambio de claves comienza con el iniciador (I) haciendo lo siguiente:

Iniciación:

1. Generar dos polinomios y con coeficientes pequeños mediante muestreo de la distribución . ${\displaystyle s_{I}}$ ${\displaystyle e_{I}}$ ${\displaystyle \chi _{\alpha }}$
2. Calcular ${\displaystyle p_{I}=as_{I}+2e_{I}.}$
3. El iniciador envía el polinomio al respondedor. ${\displaystyle p_{I}}$

Respuesta:

1. Generar dos polinomios y con coeficientes pequeños mediante muestreo de la distribución . ${\displaystyle s_{R}}$ ${\displaystyle e_{R}}$ ${\displaystyle \chi _{\alpha }}$
2. Calcular . ${\displaystyle p_{R}=as_{R}+2e_{R}}$
3. Generar un pequeño a partir de . Calcular . Luego . ${\displaystyle e'_{R}}$ ${\displaystyle \chi _{\alpha }}$ ${\displaystyle k_{R}=p_{I}s_{R}+2e'_{R}}$ ${\displaystyle k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}}$
4. Utilice la función de señal para encontrar . Esto se calcula aplicando la función a cada coeficiente de ${\displaystyle \operatorname {Sig} }$ ${\displaystyle w=\operatorname {Sig} (k_{R})}$ ${\displaystyle Sig}$ ${\displaystyle k_{R}}$
5. El flujo de claves del lado demandado se calcula basándose en la información de conciliación y el polinomio . ${\displaystyle sk_{R}=\operatorname {Mod} _{2}(k_{R},w)}$ ${\displaystyle w}$ ${\displaystyle k_{R}}$
6. El Demandado envía y al Iniciador. ${\displaystyle p_{R}}$ ${\displaystyle w}$

Finalizar:

1. Recibir y del Respondedor. ${\displaystyle p_{R}}$ ${\displaystyle w}$
2. Muestra de y Calcular . ${\displaystyle e'_{I}}$ ${\displaystyle \chi _{\alpha }}$ ${\displaystyle k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}}$
3. El flujo de claves del lado iniciador se produce a partir de la información de conciliación y el polinomio . ${\displaystyle sk_{I}=\operatorname {Mod} _{2}(k_{I},w)}$ ${\displaystyle w}$ ${\displaystyle k_{I}}$

En el intercambio de claves anterior, la función de señal se define de la siguiente manera: ${\displaystyle \operatorname {Sig} }$

Defina un subconjunto de . Aquí, y denota el piso y el redondeo al entero más cercano respectivamente. ${\displaystyle \mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}}$ ${\displaystyle Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}}$ ${\displaystyle \lfloor .\rfloor }$ ${\displaystyle \lfloor .\rceil }$

La función es la función característica del complemento de E. ${\displaystyle \operatorname {Sig} }$

${\displaystyle \operatorname {Sig} :Zq\rightarrow \{0,1\}}$: ${\displaystyle \operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}}$

${\displaystyle \operatorname {Mod} _{2}}$es la operación mod 2 para eliminar los términos de error definidos de la siguiente manera: ${\displaystyle \operatorname {Mod} _{2}(v,w)={\biggl (}v+w.{\frac {q-1}{2}}{\Biggr )}{\bmod {q}}{\bmod {2}}}$

Tenga en cuenta que los valores de y son aproximadamente iguales. Para extraer una clave compartida utilizando estos valores aproximadamente iguales, se utiliza una función de reconciliación, también conocida como función de señal. Esta función indica la región en la que se encuentra cada coeficiente de un polinomio en y ayuda a garantizar que los términos de error en y no den como resultado operaciones de módulo q diferentes. ${\displaystyle k_{I}}$ ${\displaystyle k_{R}}$ ${\displaystyle v}$ ${\displaystyle R_{q}}$ ${\displaystyle k_{R}}$ ${\displaystyle k_{I}}$

Los métodos de conciliación y generación de cadenas de claves dependen del esquema RLWE-KEX específico en cuestión. Algunos métodos se basan en aritmética modular, mientras que otros pueden basarse en geometría de alta dimensión. ^{[6] [11]}

Si el intercambio de claves funcionó correctamente, la cadena del iniciador y la cadena del respondedor serán la misma.

Dependiendo de las particularidades de los parámetros elegidos, existe una probabilidad extremadamente pequeña de que este intercambio de claves no produzca la misma clave. Los parámetros para el intercambio de claves pueden elegirse de modo que la probabilidad de falla en el intercambio de claves sea muy pequeña; mucho menor que la probabilidad de errores indetectables o fallas del dispositivo.

Opciones de parámetros

El intercambio RLWE-KEX presentado anteriormente funcionó en el Anillo de polinomios de grado n  − 1 o menor módulo un polinomio . La presentación supuso que n era una potencia de 2 y que q era un primo congruente con 1 (mód 2n). Siguiendo la guía dada en el artículo de Peikert, Singh sugirió dos conjuntos de parámetros para el RLWE-KEX. ${\displaystyle \Phi (x)}$

Para 128 bits de seguridad, n = 512, q = 25601 y ${\displaystyle \Phi (x)=x^{512}+1}$

Para 256 bits de seguridad, n = 1024, q = 40961 y ${\displaystyle \Phi (x)=x^{1024}+1}$

Debido a que el intercambio de claves utiliza un muestreo aleatorio y límites fijos, existe una pequeña probabilidad de que el intercambio de claves no produzca la misma clave para el iniciador y el respondedor. Si suponemos que el parámetro gaussiano σ es y el límite de muestreo uniforme ( b ) = 5 (véase Singh), ^[6] entonces la probabilidad de que falle el acuerdo de claves es menor que 2 ⁻⁷¹ para los parámetros seguros de 128 bits y menor que 2 ⁻⁹¹ para los parámetros seguros de 256 bits. ${\textstyle {\frac {8}{\sqrt {2\pi }}}}$

En su artículo de noviembre de 2015, Alkim, Ducas, Pöppelmann y Schwabe recomiendan los siguientes parámetros n = 1024, q = 12289 y = x ¹⁰²⁴ + 1. ^[11] Esto representa una reducción del 70 % en el tamaño de la clave pública sobre los parámetros n = 1024 de Singh, y se presentó al proyecto de Estandarización de Criptografía Post-Cuántica del NIST con el nombre NewHope . ${\displaystyle \Phi (x)}$

También en su artículo de noviembre de 2015, Alkim, Ducas, Pöppelmann y Schwabe recomiendan que la elección del polinomio base para el intercambio de claves (a(x) arriba) se genere aleatoriamente a partir de un generador de números aleatorios seguro para cada intercambio o se cree de manera verificable utilizando una técnica de "nada bajo la manga" o NUMS. ^[11] Un ejemplo de parámetros generados de esta manera son los números primos para el Intercambio de Claves de Internet (RFC 2409) que incrustan los dígitos de la constante matemática pi en la representación digital del número primo. ^[12] Su primer método evita la amortización de los costos de ataque en muchos intercambios de claves con el riesgo de dejar abierta la posibilidad de un ataque oculto como el descrito por Dan Bernstein contra las curvas elípticas del NIST. ^[13] El enfoque NUMS está abierto a la amortización, pero generalmente evita el ataque de Bernstein si solo se utilizan constantes matemáticas comunes como pi y e.

Seguridad del intercambio de claves

La seguridad de este intercambio de claves se basa en la dificultad subyacente del problema de aprendizaje de anillo con errores que ha demostrado ser tan difícil como la solución del peor caso para el problema del vector más corto (SVP) en una red ideal . ^{[1] [2]} El mejor método para medir la seguridad práctica de un conjunto dado de parámetros de red es el algoritmo de reducción de red BKZ 2.0. ^[14] Según el algoritmo BKZ 2.0, los parámetros de intercambio de claves enumerados anteriormente proporcionarán más de 128 o 256 bits de seguridad, respectivamente.

Implementaciones

En 2014, Douglas Stebila creó un parche para OpenSSL 1.0.1f basado en su trabajo y otros publicados en "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem" [Intercambio de claves postcuánticas para el protocolo TLS a partir del problema del aprendizaje en anillo con errores]. ^[15] El software que implementa el trabajo de Singh se encuentra en GitHub en https://github.com/vscrypto/ringlwe. ^[6]

Otros enfoques

Una variante del enfoque descrito anteriormente es una versión autenticada en el trabajo de Zhang, Zhang, Ding, Snook y Dagdelen en su artículo, "Post Quantum Authenticated Key Exchange from Ideal Lattices". ^[16] El concepto de crear lo que se ha llamado un intercambio de claves de tipo Diffie-Hellman utilizando redes con una función de reconciliación parece haber sido presentado por primera vez por los investigadores franceses Aguilar, Gaborit, Lacharme, Schrek y Zemor en PQCrypto 2010 en su charla, "Noisy Diffie-Hellman Protocols". ^[17]

En noviembre de 2015, Alkim, Ducas, Pöppelmann y Schwabe se basaron en el trabajo previo de Peikert y utilizaron lo que creen que es un cálculo de costos más conservador de los ataques de red para recomendar parámetros. ^[11] El software basado en el trabajo de Alkim, Ducas, Pöppelmann y Schwabe se encuentra en GitHub en https://github.com/tpoeppelmann/newhope ^[11]

Véase también

• Criptografía post-cuántica
• Criptografía basada en celosía
• Criptografía de red ideal
• Aprendizaje de anillos con firma de errores
• Aprendizaje de anillos con errores

Referencias

1. Regev, Oded (2005). "Sobre redes, aprendizaje con errores, códigos lineales aleatorios y criptografía". Actas del trigésimo séptimo simposio anual de la ACM sobre teoría de la computación . STOC '05. Nueva York, NY, EE. UU.: ACM. pp. 84–93. CiteSeerX  10.1.1.110.4776 . doi :10.1145/1060590.1060603. ISBN . 978-1-58113-960-0.S2CID53223958  .​
2. Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012). Un esquema de intercambio de claves simple y demostrablemente seguro basado en el problema de aprendizaje con errores (PDF) .
3. Peikert, Chris (1 de enero de 2014). "Criptografía en red para Internet". Archivo de ePrints de criptología .
4. Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (1 de enero de 2015). "Intercambio de claves postcuántico: una nueva esperanza". Archivo de ePrints de criptología .
5. "Experimentando con criptografía post-cuántica". Blog de seguridad en línea de Google . Consultado el 8 de febrero de 2017 .
6. Singh, Vikram (2015). "Un intercambio práctico de claves para Internet mediante criptografía en red". Archivo de ePrints de criptología .
7. "Archivo de ePrints de criptología: Informe 2015/1120". eprint.iacr.org . Consultado el 23 de diciembre de 2015 .
8. "Un muestreador gaussiano eficiente y paralelo para redes" (PDF) . www.cc.gatech.edu . Consultado el 29 de mayo de 2015 .
9. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2013). "Un conjunto de herramientas para la criptografía Ring-LWE". Archivo de ePrints de criptología .
10. "Archivo de ePrints de criptología: Informe 2015/1120". eprint.iacr.org . Consultado el 17 de enero de 2016 .
11. "Archivo de ePrints de criptología: Informe 2015/1092". eprint.iacr.org . Consultado el 11 de noviembre de 2015 .
12. D., Carrel; D., Harkins (noviembre de 1998). "Intercambio de claves de Internet (IKE)". tools.ietf.org . Consultado el 16 de marzo de 2017 .
13. "¿Es vulnerable el intercambio de claves en red "New Hope" a un análogo en red del ataque BADA55 de Bernstein?". crypto.stackexchange.com . Consultado el 16 de marzo de 2017 .
14. Chen, Yuanmi; Nguyen, Phong Q. (2011). "BKZ 2.0: Mejores estimaciones de seguridad de la red". En Lee, Dong Hoon; Wang, Xiaoyun (eds.). Avances en criptología – ASIACRYPT 2011. Apuntes de clase en informática. Vol. 7073. Springer Berlin Heidelberg. págs. 1–20. doi :10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
15. Bos, Joppe W.; Costello, Craig; Naehrig, Michael; Stebila, Douglas (1 de enero de 2014). "Intercambio de claves postcuántico para el protocolo TLS a partir del problema de aprendizaje en anillo con errores". Archivo de ePrints de criptología .
16. "Taller sobre ciberseguridad en un mundo post-cuántico". NIST . 2 de abril de 2015 . Consultado el 6 de junio de 2015 .
17. "Noisy Diffie–Hellman protocols" (PDF) . pqc2010.cased.de . Archivado desde el original (PDF) el 2015-06-14 . Consultado el 2015-06-06 .

Enlaces externos