Informe sobre criptografía post-cuántica

3. Planteamientos

Existen distintas áreas desde las que se enfocan las principales construcciones post-cuánticas, algunas procedentes de escenarios matemáticos clásicos que no han sido, hasta ahora, explotados en aplicaciones criptográficas. Muchas de las áreas que mencionaremos sólo sirven para plantear herramientas de un cierto tipo (por ejemplo, cifrado o firma digital), y algunas ya se consideran descartadas a la luz de los resultados que arroja la primera ronda de evaluación procedente de la competición del NIST.

3.1. Criptografía basada en Grupos

En los últimos quince años se han propuesto de manera continua herramientas criptográficas que tomaban como base problemas matemáticos descritos en grupos no abelianos. Muchas veces, el argumento de su resistencia a algoritmos cuánticos se ha esgrimido como un acicate a este área. Sin embargo, existen serias dudas de la seguridad de muchas de estas construcciones (incluso sin necesidad de recurrir a criptanálisis cuánticos).

Muchas de estas propuestas se basan en la idea de sustituir construcciones basadas en teoría de números, como el esquema de intercambio de claves de Diffie-Hellman, por una especie de diseño análogo no-abeliano, donde las exponenciaciones modulares se sustituyen por conjugaciones en el grupo utilizado. Tales diseños se han propuesto sobre grupos de trenzas o grupos de matrices, siempre con escaso éxito (como señalamos en el trabajo [14]). El monográfico [13] recoge las principales propuestas en ese ámbito, y señala los problemas de seguridad detectados en las mismas.

Por último, creemos oportuno mencionar que existe una vía abierta de trabajo, las construcciones simétricas basadas en el Hidden Shift Problem [1], mucho más prometedora que las propuestas que hemos mencionado.

3.2. Criptografía basada en Códigos

En esta sección hablaremos de criptografía basada en códigos, centrando nuestro análisis en el esquema de cifrado de clave pública McEliece [20] y sus variantes. A grandes rasgos, el problema subyacente a este tipo de construcciones es el de decodificar una palabra codificada a través de un código lineal desconocido. Dicho código se describe a través de 3 parámetros: n y k, que hacen referencia a la longitud y dimensión del código, y t, que es el número de errores que es posible corregir en una codificación errónea. Así, una matriz G de dimensión n × k sirve para generar palabras codificadas: las palabras (vectores binarios de longitud k) se codifican como vectores de longitud n al multiplicarse por G. De la misma forma, si existe un error en la transmisión traducible en un vector e binario con peso de Hamming¹ acotado por t, existe un algoritmo de decodificación asociado a G que permite recuperar la palabra original.

Para construir un cifrado de clave pública a partir de esta idea, se siguen los siguientes pasos:

• Alice selecciona una matriz G asociada a un código de parámetro (n,k,t) y la ofusca transformándola en una matriz Ĝ. La clave secreta servirá para revertir este proceso, recuperando G a partir de Ĝ. La clave pública es el par (Ĝ,t).
• Bob cifra un mensaje m ∈{0, 1}^k como c = mĜ+e, siendo e un vector aleatorio que contiene exactamente t unos.
• Alice recupera m usando el algoritmo de corrección-decodificación asociado a G.

3.2.1. Cifrado McEliece

Es el ejemplo más destacado de cifrado basado en códigos. Fue propuesto en 1998 y se fundamenta en la idea anterior, siendo G la matriz asociada a ciertos códigos lineales llamados códigos de Goppa. Los parámetros sugeridos originalmente eran n = 1024,k = 524 y t = 50, si bien las propuestas actuales para seguridad de 80 bits son distintas, resultando en claves públicas de tamaños desorbitados (en torno a 500.000 bits). Para los parámetros sugeridos con el fin de conseguir seguridad post-cuántica, n = 6960, k = 5413 y t = 119, el tamaño de las claves usando códigos de Goppa está por encima de los ocho millones de bits, siendo éste el principal inconveniente de este tipo de cifrado. Por otro lado, las operaciones de cifrado y descifrado son relativamente eficientes, y los resultados de seguridad resultan esperanzadores y permiten establecer pautas claras para la generación de claves ajustada al nivel de seguridad perseguido.

3.2.2. Criptanálisis

Aunque el principal obstáculo a la extensión del esquema de MacEliece tiene que ver con la eficiencia, en su larga historia han aparecido multitud de ataques (casi siempre a implementaciones concretas) y contramedidas asociadas, que pueden resultar de utilidad a la hora de tomar decisiones hacia un nuevo desarrollo. En concreto, destacamos las siguientes lineas de ataque/investigación:

• Algoritmos para resolver el problema general de decodificación de códigos binarios. El ataque de Stern y la mejora posterior de Canteaut-Chabaud (ver [5]) utilizando esta técnica obligó a cambiar los parámetros originalmente propuestos para McEliece y a ampliar los tamaños de clave de 88 a 130 KBytes. Desde 1995 apenas ha habido avances en estas lineas, aunque líneas de trabajo como la llamada “decodificación iterativa” [12] o “decodificación estadística” [19] son susceptibles de dar resultados notables.
• Algoritmos para decodificar otros códigos. Si en un intento de conseguir claves más cortas se reemplazan los códigos Goppa utilizados habitualmente en las implementaciones por otros, los algoritmos de decodificación pueden resultar más efectivos, y por tanto los esquemas resultan más débiles. Así se ha demostrado, por ejemplo, para esquemas propuestos con códigos GRS y códigos de Reed-Muller (ver  [21]).
• Ataques por canales colaterales (side-channel attacks). Fijada una implementación concreta, en ocasiones este tipo de ataques son muy efectivos, extrayendo valiosa información a través de patrones dependientes de la implementación (o incluso del dispositivo concreto que la ejecuta). Los más exitosos en cuanto a MacEliece son los ataques de tipo DPA (que miden diferencias en cuanto al consumo eléctrico) y otros llamados verticales/horizontales asociados a ciertas implementaciones (ver [6, 8]). Existen técnicas de enmascaramiento para corregir las implementaciones vulnerables a estos ataques (ver por ejemplo [7]), si bien toda implementación desarrollada debería (como indican las buenas prácticas criptográficas) revisarse en este sentido evitando la filtración de patrones.

3.3. Criptografía Multivariable

La criptografía multivariante se articula alrededor de problemas asociados a la resolución de sistemas de ecuaciones no lineales en varias variables sobre cuerpos finitos. Típicamente, se publican m polinomios p₁,…,p_m de n variables y grado bajo d sobre un cuerpo finito F (caso más habitual: d = 2). Para descifrar, autenticarse o firmar digitalmente un usuario se enfrenta al reto de, dado z = (z₁,…,z_m) ∈ F^m encontrar una solución w = (w ₁,…,w_n) para el sistema asociado:

Algunos de los esquemas más destacados en esta línea son:

• La firma QUARTZ [22], que destaca por producir firmas muy cortas (100 bits).
• El cifrado ZHFE [23], para el que aún no se dispone de una demostración de seguridad.

Pese a las ventajas que estos esquemas pueden presentar (como su flexibilidad para ser implementados en distintas plataformas), existen serias dudas sobre la seguridad que alcanzan. Otro inconveniente (menor) que presentan es que el tamaño de sus claves es bastante grande. Para más información, ver [11].

3.4. Criptografía basada en Retículos

Desde 1998, se ha evaluado la utilidad de problemas difíciles sobre retículos a la hora de construir herramientas criptográficas. Las técnicas computacionales para retículos de enteros fueron fundamentales para el criptanálisis de los primeros esquemas combinatorios de cifrado, así como para evaluar la robustez de las claves utilizadas por el esquema RSA o las funciones hard-core asociadas a funciones unidireccionales. En los últimos años, sin embargo, su papel ha sido distinto al proporcionar construcciones para cifrado homomórfico y potencialmente resistente a criptanálisis cuántico.

3.4.1. Fundamentos matemáticos

La mayoría de los esquemas de cifrado de clave pública basados en retículos se basan en el problema designado con las siglas LWE (learning with errors).

El problema LWE. Sea n ∈ ℕ y consideremos q un entero positivo (cuyo tamaño en bits es similar a n). Consideremos n vectores ₁,…,_n cuyas coordenadas están en ℤ_q. El retículo Λ generado por la base de vectores B = {₁,…,_n} queda definido por:

Con frecuencia, para hacer explícita la base, Λ se denota ℒ(B).

Una instance del problema LWE se plantea de la siguiente manera: consideremos fijado un vector secreto con n coordenadas en ℤ_q.²

1. Elegimos un vector ∈ ℤ_qⁿ.
2. Elegimos un error e al azar según una distribución T, donde T es una cierta distribución de probabilidad.³
3. Calculamos el producto escalar de y , que denotaremos ⟨,⟩.
4. Definimos t = ⟨,⟩ + e (mod q).
5. Damos como salida el par (,t) ∈ ℤ_qⁿ × ℤ _q.

Se plantea entonces el problema de como recuperar dada una colección de pares {(_i,t_i) ∈ ℤ_qⁿ × ℤ _q}_i=1,…m construidos mediante el proceso anterior. La dificultad de este problema depende de cómo elijamos la distribución T y los parámetros n y q. Con frecuencia, la distribución T es una distribución llamada distribución Gaussiana discreta que depende de un parámetro real positivo s. Así, lo habitual es definir cada instancia concreta de LWE a partir de los tres parámetros (n,q,s).⁴ Hay una versión decisional del problema anterior, que plantea distinguir los valores t₁,…,t_m de valores seleccionados al azar en ℤ_q.

Desafortunadamente, no resulta sencillo dar una evaluación de seguridad estricta que permita conocer cómo influyen los parámetros (n,q,s) en la dificultad del problema anterior. Aunque esta cuestión es objeto de numerosos trabajos actuales (ver, por ejemplo [16]), los expertos no han conseguido explicitar qué impacto tiene tomar, por ejemplo, dimensiones n mayores o menores en la seguridad de los esquemas criptográficos asociados. Existen recomendaciones basadas esencialmente en ataques heurísticos (ver por ejemplo [26]).

3.4.2. Propuestas

Existen distintas propuestas para construir cifrado de clave pública a partir de este problema y de problemas relacionados, como el llamado problema del vector más próximo o closest vector problem. Mencionamos los más destacados:

• Esquema de Regev [24]: primera propuesta basada en LWE. Esencialmente académica.
• NTRU [17]: propuesto en 1998, no es completamente homomórfico pero mantiene bien la estructura para un número prefijado de cálculos con dos operaciones no demasiado grande (según implementaciones).
• BGV [4]: completamente homomórfico, implementado en la librería HELib. Es una variante del aclamado esquema de Gentry que usa el problema LWE sobre anillos (llamado también RLWE).

Hacemos mención especial al trabajo reciente [2], que puede servir como puente entre nuestros recientes resultados para la construcción de claves en grupos utilizando hash-proof systems y el escenario post-cuántico. Más concretamente, muchas construcciones criptográficas basadas en hash-proof systems pasarían a ser post-cuánticas gracias estos resultados (por ejemplo, nuestro esquema para la intersección privada propuesto en [10]).

3.5. Criptografía basada en Hashes

Una función hash o función resumen, es simplemente una aplicación que transforma cadenas de bits de longitud arbitraria en cadenas de longitud prefijada. Estas funciones se utilizan ampliamente en criptografía, esencialmente para construir pruebas de integridad o acelerar la comparación de valores. En el primer caso, un valor H(m), trasmitido junto a un mensaje, proporciona una etiqueta para verificar si m se ha modificado en el proceso de trasmisión. En el segundo, por ejemplo, es frecuente almacenar hashes de contraseñas (en lugar de contraseñas de usuarios) a la hora de establecer mecanismos de control de acceso. Un requerimiento imprescindible para la mayoría de los usos de funciones hash, es que sea difícil encontrar colisiones, es decir, dos valores distintos cuyos resumenes (imagenes por la función hash H) coincidan.

Muchas de las funciones hash utilizadas en la actualidad serían vulnerables a ataques cuánticos que utilizasen el algoritmo de Grover. La manera trivial de evitar dichos ataques, neutralizando la ventaja cuadrática en búsquedas no estructuradas que da el algoritmo de Grover, es doblar el rango de los hashes para cualquiera de sus usos. La criptografía basada en funciones hash tiene especial interés en el escenario post-cuántico dentro del escenario de la firma digital. En principio, las firmas construidas con hashes usando los llamados árboles de Merkle constituyen los candidatos más sólidos para firmas post-cuánticas, destacando los esquemas XMSS y SPHINCs (ver [18, 3])— siempre con claves de 256 bits.

Informalmente un árbol de Merkle se describe como una estructura de datos en árbol, binario o no, de modo que cada nodo que no es una hoja está etiquetado con el hash de la concatenación de las etiquetas o valores de sus hijos. De este modo, se posibilita que un gran número de datos separados puedan ser ligados a un único valor de hash, el hash del nodo raíz del árbol. A través de esta estructura puede definirse por tanto un método de verificación segura y eficiente de los contenidos de grandes estructuras de datos.