Aprendizaje en anillo 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, la cual pueden usar para cifrar mensajes entre ellas. El algoritmo de intercambio de claves de aprendizaje de anillos con errores ( RLWE-KEX ) pertenece a una nueva clase de algoritmos de intercambio de clave pública diseñados para ser seguros frente a un adversario con una computadora cuántica . Esto es importante porque algunos algoritmos de clave pública en uso actualmente serían fácilmente vulnerados por una computadora cuántica si se implementara. RLWE -KEX es uno de los algoritmos criptográficos postcuánticos basados ​​en la dificultad de resolver ciertos problemas matemáticos que involucran retículos . A diferencia de los algoritmos criptográficos basados ​​en retículos más antiguos, RLWE -KEX es demostrablemente reducible a un problema difícil conocido en retículos.

Desde la década de 1980, la seguridad de los intercambios de claves criptográficas y las firmas digitales en 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 computacionalmente 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 campo 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 la actualidad), pero se resuelven con relativa facilidad en una computadora cuántica relativamente pequeña que utiliza solo de 5 a 10 mil bits de memoria. Existe optimismo en la industria informática respecto a que las computadoras cuánticas a 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ásicamente difíciles serían inseguros. Esta criptografía de clave pública se utiliza hoy en día para proteger los sitios web de Internet, salvaguardar la información de inicio de sesión de los ordenadores e impedir que nuestros ordenadores acepten software malicioso.

La criptografía que no es susceptible a ataques de una computadora cuántica se denomina criptografía cuántica segura o postcuántica . Una clase de algoritmos criptográficos resistentes a la computación 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 cuerpo finito . Esta forma especializada se denomina aprendizaje de anillos con errores o RLWE .

Existen diversos algoritmos criptográficos que funcionan utilizando el paradigma RLWE. Además del algoritmo de intercambio de claves de clave pública presentado 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 interlocutores en un enlace de comunicación. El ejemplo clásico de intercambio de claves es el Diffie-Hellman . Este intercambio consiste en una transmisión desde un extremo de la línea y otra 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 una alternativa " cuánticamente segura " a los intercambios de claves Diffie-Hellman y Diffie-Hellman de curva elíptica , ampliamente utilizados para garantizar el establecimiento de claves secretas a través de 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 denominada " secreto hacia adelante ", cuyo objetivo es reducir la eficacia de los programas de vigilancia masiva y asegurar que no existan claves secretas a largo plazo que puedan verse comprometidas y que permitan el descifrado masivo.

Partiendo de un número primo q, el intercambio de claves Ring-LWE funciona en el anillo de polinomios módulo un polinomio.${\displaystyle \Phi (x)}$con coeficientes en el campo de los enteros módulo q (es decir, el anillo${\displaystyle R_{q}:=Z_{q}[x]/\Phi (x)}$La multiplicación y la suma de polinomios funcionarán de la manera habitual, con los resultados de una multiplicación reducidos.${\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 se basa en la asociatividad de las multiplicaciones de matrices, y los errores se utilizan para proporcionar seguridad. El artículo ^{[ 2 ]} se publicó en 2012 tras la presentación de una solicitud de patente provisional ese mismo año. La seguridad del protocolo se demuestra 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 redondeo en la construcción de Ding.

La implementación "New Hope" ^{[ 4 ]} seleccionada para el experimento post-cuántico de Google, ^{[ 5 ]} utiliza el esquema de Peikert con variación en la distribución de errores.

Para una seguridad ligeramente superior a 128 bits , 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 posteriormente 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${\displaystyle a_{i}}$de este polinomio son enteros  módulo q . El polinomio ${\displaystyle \Phi (x)}$será el polinomio ciclotómico . Cuando n es una potencia de 2, entonces${\displaystyle \Phi (x)=x^{n}+1.}$^{[ 6 ] [ 7 ]}

El RLWE-KEX utiliza polinomios que se consideran "pequeños" con respecto a una medida llamada " norma infinito ". La norma infinito para un polinomio es simplemente el valor del coeficiente más grande del polinomio cuando los coeficientes se consideran como enteros en Z en lugar de${\displaystyle Zq}$(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 infinito. Esto se logra simplemente generando aleatoriamente los coeficientes de un polinomio ( s _n-1 , ..., s ₀ ) que están garantizados o son muy probables que sean pequeños. Hay dos formas comunes de hacer esto:

1. Usando muestreo uniforme : los coeficientes del pequeño polinomio se muestrean uniformemente de un conjunto de coeficientes pequeños. Sea b un entero 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. Mediante muestreo gaussiano discreto : para un valor impar de q, los coeficientes se eligen aleatoriamente mediante 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 detalle cómo se puede lograr esto. Es más complejo que el muestreo uniforme, pero permite demostrar la seguridad del algoritmo. Una descripción general del muestreo gaussiano se encuentra en una presentación de Peikert. ^{[ 8 ]} 

Para el resto de este artículo, los polinomios pequeños aleatorios se muestrearán según una distribución que se especifica simplemente como D. Además, q será un primo impar tal que q es congruente con 1 mod 4 y 1 mod 2n. Otros casos para q y n se discuten en detalle 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 determinísticamente a partir de una fuente criptográficamente segura.

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

El intercambio de claves se realizará entre dos dispositivos. Habrá un iniciador para el intercambio de claves designado como (I) y un receptor designado como (R). Tanto I como R conocen q , n , a ( x ) y tienen la capacidad de generar polinomios pequeños de acuerdo con la distribución.${\displaystyle \chi _{\alpha }}$con parámetro${\displaystyle \alpha }$La distribución${\displaystyle \chi _{\alpha }}$Suele ser la distribución gaussiana discreta en el anillo.${\displaystyle R_{q}=Z_{q}[x]/\Phi (x)}$La descripción que sigue no explica por qué el intercambio de claves da como resultado la misma clave en ambos extremos de un enlace. En cambio, especifica de forma concisa los pasos a seguir. Para comprender en profundidad 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 Ding et al. ^{[ 2 ] citado.}

El intercambio de claves comienza cuando el iniciador (yo) realiza lo siguiente:

Iniciación:

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

Respuesta:

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

Finalizar:

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

En el intercambio de claves anterior,${\displaystyle \operatorname {Sig} }$La función de señal se define como se indica a continuación:

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

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

${\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 módulo 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${\displaystyle k_{I}}$y${\displaystyle k_{R}}$ son solo 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 cada coeficiente de un polinomio${\displaystyle v}$en${\displaystyle R_{q}}$mentiras y ayuda a asegurarse de que los términos de error en${\displaystyle k_{R}}$y ${\displaystyle k_{I}}$no dan como resultado operaciones mod q diferentes.

Los métodos de reconciliació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 idénticas.

Dependiendo de los parámetros seleccionados, la probabilidad de que este intercambio de claves no genere la misma clave es extremadamente baja. Los parámetros del intercambio de claves pueden elegirse para que la probabilidad de fallo sea mínima, mucho menor que la de errores indetectables o fallos del dispositivo.

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

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 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 asumimos que el parámetro gaussiano σ es${\textstyle {\frac {8}{\sqrt {2\pi }}}}$y el límite de muestreo uniforme ( b ) = 5 (ver Singh), ^{[ 6 ]} entonces la probabilidad de fallo de acuerdo de clave es menor que 2 ^-71 para los parámetros seguros de 128 bits y menor que 2 ^-91 para los parámetros seguros de 256 bits.

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

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 "nothing up my sleeve" 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 a 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.

La seguridad de este intercambio de claves se basa en la dificultad subyacente del problema de aprendizaje de anillos con errores , que ha demostrado ser tan difícil como la solución del peor caso al 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.

En 2014, Douglas Stebila creó un parche para OpenSSL 1.0.1f. basado en su trabajo y otros publicados en "Intercambio de claves post-cuántico 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 ]}

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, "Intercambio de claves autenticado post-cuántico a partir de retículos ideales". ^{[ 16 ]} El concepto de crear lo que se ha llamado un intercambio de claves tipo Diffie-Hellman utilizando retículos 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, "Protocolos Diffie-Hellman ruidosos". ^{[ 17 ]}

En noviembre de 2015, Alkim, Ducas, Pöppelmann y Schwabe se basaron en el trabajo previo de Peikert y utilizaron lo que consideran un cálculo de costos más conservador para los ataques de retículos con el fin de 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 ]}

• Criptografía postcuántica
• Criptografía basada en retículos
• Criptografía reticular ideal
• Aprendizaje en anillo con firma de errores
• Aprendizaje en anillo con errores