3.1 Introducción a Problemas Matemáticos Resistentes a Ataques Cuánticos

La criptografía post-cuántica se basa en problemas matemáticos que se consideran difíciles incluso para computadoras cuánticas. Estos problemas tienen características específicas que los hacen resistentes al algoritmo de Shor y otros algoritmos cuánticos conocidos.

Características de Problemas Resistentes a Ataques Cuánticos

• No Reducibles a Factorización o Logaritmos Discretos: Deben ser fundamentalmente diferentes de los problemas que el algoritmo de Shor puede resolver eficientemente.
• Resistencia a Transformadas Cuánticas de Fourier: No deben tener una estructura periódica que pueda ser explotada por transformadas cuánticas.
• Complejidad Demostrable: Idealmente, deben tener pruebas formales de su dificultad o reducciones a problemas bien estudiados.
• Historia de Análisis Criptográfico: Preferiblemente, problemas que han sido estudiados durante años y han resistido intentos de solución.

Principales Categorías de Problemas

Los problemas matemáticos utilizados en criptografía post-cuántica se pueden clasificar en varias categorías principales:

• Problemas de Retículos: Encontrar vectores cortos o cercanos en estructuras matemáticas llamadas retículos.
• Problemas de Códigos: Decodificar códigos aleatorios sin conocer una estructura especial.
• Problemas Multivariables: Resolver sistemas de ecuaciones polinómicas multivariables.
• Problemas de Isogenias: Encontrar mapeos específicos entre curvas elípticas.
• Problemas Basados en Hash: Explotar propiedades de funciones hash para construir esquemas de firma.

Comparación con Problemas Clásicos

Problema Clásico	Problema Post-Cuántico	Diferencia Clave
Factorización de Enteros (RSA)	Problema del Vector más Corto (SIS)	No tiene estructura periódica explotable por QFT
Logaritmo Discreto (ECC)	Learning With Errors (LWE)	Incluye ruido aleatorio que dificulta ataques cuánticos
Problema del Logaritmo Discreto en Curvas Elípticas	Problema de Isogenias Supersingulares	Basado en mapeos entre curvas, no en operaciones dentro de una curva

3.2 Criptografía Basada en Retículos

La criptografía basada en retículos es una de las aproximaciones más prometedoras para la criptografía post-cuántica, con algoritmos como ML-KEM (anteriormente Kyber) y ML-DSA (anteriormente Dilithium) seleccionados por el NIST para estandarización.

Fundamentos de Retículos

Un retículo es un conjunto de puntos en un espacio n-dimensional con una estructura regular y repetitiva.

• Definición Formal: Un retículo L es el conjunto de todas las combinaciones lineales enteras de un conjunto de vectores base linealmente independientes: L = {a₁v₁ + a₂v₂ + ... + aₙvₙ | aᵢ ∈ ℤ}.
• Base del Retículo: Conjunto de vectores linealmente independientes que generan el retículo. Un mismo retículo puede tener múltiples bases.
• Determinante: Volumen del paralelotopo fundamental, mide la "densidad" del retículo.

Problemas Computacionales en Retículos

• Problema del Vector más Corto (SVP): Encontrar el vector no nulo más corto en un retículo.
• Problema del Vector más Cercano (CVP): Dado un punto arbitrario, encontrar el punto del retículo más cercano.
• Short Integer Solution (SIS): Encontrar una combinación lineal corta de vectores que sume cero módulo q.
• Learning With Errors (LWE): Distinguir entre muestras aleatorias y muestras con una estructura lineal oculta perturbada por pequeños errores.
• Ring-LWE y Module-LWE: Variantes más eficientes de LWE que operan en estructuras algebraicas específicas.

Algoritmos Basados en Retículos

• ML-KEM (Kyber): Mecanismo de encapsulamiento de claves basado en Module-LWE, seleccionado por el NIST para estandarización (FIPS 203).
• ML-DSA (Dilithium): Esquema de firma digital basado en Module-LWE, seleccionado por el NIST para estandarización (FIPS 204).
• NTRU: Uno de los primeros sistemas criptográficos basados en retículos, basado en el problema de encontrar divisores cortos de polinomios.
• Falcon: Esquema de firma que utiliza técnicas de muestreo gaussiano para generar firmas cortas.

Ventajas y Desventajas

Ventajas:

• Basados en problemas bien estudiados con reducciones de seguridad.
• Relativamente eficientes en comparación con otras familias post-cuánticas.
• Versátiles, permitiendo cifrado, firmas y otras primitivas criptográficas.
• Parámetros ajustables para diferentes niveles de seguridad.

Desventajas:

• Claves y firmas más grandes que en criptografía clásica.
• Complejidad matemática que puede dificultar implementaciones correctas.
• Algunos esquemas requieren generación de números aleatorios de alta calidad.

3.3 Criptografía Basada en Códigos

La criptografía basada en códigos utiliza la teoría de códigos correctores de errores para construir sistemas criptográficos resistentes a ataques cuánticos. Es una de las aproximaciones más antiguas a la criptografía post-cuántica.

Fundamentos de Códigos Correctores de Errores

• Código Lineal: Subespacio vectorial de Fⁿq donde Fq es un campo finito.
• Matriz Generadora (G): Define cómo codificar mensajes.
• Matriz de Paridad (H): Define cómo verificar si un vector pertenece al código.
• Distancia Mínima: Mínimo número de posiciones en que difieren dos palabras código distintas.
• Capacidad de Corrección: Número máximo de errores que el código puede corregir.

Problemas Computacionales en Códigos

• Problema de Decodificación de Síndrome (SDP): Dado un síndrome, encontrar un vector de error de peso mínimo que lo produzca.
• Problema de Decodificación por Distancia Mínima: Encontrar la palabra código más cercana a un vector dado.
• Problema de Decodificación General: Decodificar un código aleatorio sin conocer una estructura especial.

Algoritmos Basados en Códigos

• McEliece: Uno de los primeros sistemas post-cuánticos, propuesto en 1978, basado en códigos de Goppa.
• Classic McEliece: Versión moderna del sistema McEliece, finalista en el proceso de estandarización del NIST.
• BIKE (Bit Flipping Key Encapsulation): Basado en códigos QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check).
• HQC (Hamming Quasi-Cyclic): Combina códigos BCH con el problema de decodificación de códigos aleatorios.

Ventajas y Desventajas

Ventajas:

• Larga historia de análisis criptográfico (McEliece ha resistido ataques durante más de 40 años).
• Operaciones de cifrado rápidas.
• Basados en problemas bien estudiados en teoría de códigos.

Desventajas:

• Claves públicas muy grandes (especialmente en Classic McEliece).
• Menos versátiles que los sistemas basados en retículos.
• Algunos esquemas tienen tasas de decodificación fallida no nulas.

3.4 Criptografía Basada en Isogenias

La criptografía basada en isogenias utiliza mapeos especiales entre curvas elípticas llamados isogenias. Aunque es un área relativamente nueva, ofrece algunas de las claves más compactas entre los sistemas post-cuánticos.

Fundamentos de Curvas Elípticas e Isogenias

• Curva Elíptica: Conjunto de puntos que satisfacen una ecuación de la forma y² = x³ + ax + b.
• Isogenia: Mapeo racional entre curvas elípticas que preserva la estructura de grupo.
• Curvas Supersingulares: Clase especial de curvas elípticas con propiedades matemáticas particulares.
• Grafo de Isogenias: Grafo cuyos vértices son curvas elípticas y las aristas son isogenias entre ellas.

Problemas Computacionales en Isogenias

• Problema de Camino de Isogenias Supersingulares (SSIP): Encontrar un camino de isogenias entre dos curvas supersingulares.
• Problema de Acción de Isogenias Conmutativas (CSIA): Recuperar una acción de grupo a partir de su resultado.

Algoritmos Basados en Isogenias

• SIKE (Supersingular Isogeny Key Encapsulation): Basado en isogenias entre curvas elípticas supersingulares. Fue un candidato en el proceso del NIST pero se rompió en 2022.
• CSIDH (Commutative Supersingular Isogeny Diffie-Hellman): Utiliza la acción de un grupo de clase en curvas supersingulares.
• SQISign (Short Quantum-resistant Isogeny-based Signatures): Esquema de firma basado en isogenias con firmas compactas.

Ventajas y Desventajas

Ventajas:

• Claves muy compactas en comparación con otros sistemas post-cuánticos.
• Estructura matemática elegante y bien fundamentada.
• Potencial para esquemas con propiedades especiales (como homomorfismo).

Desventajas:

• Área relativamente nueva con menos análisis criptográfico.
• Operaciones computacionalmente intensivas.
• Algunos esquemas (como SIKE) han sido vulnerables a ataques inesperados.

Estado Actual

La criptografía basada en isogenias sufrió un revés significativo cuando SIKE fue roto en 2022 mediante un ataque inesperado basado en torsión. Sin embargo, este ataque no afecta a todos los sistemas basados en isogenias, y la investigación continúa en esquemas alternativos como CSIDH y SQISign.

3.5 Criptografía Multivariable

La criptografía multivariable se basa en la dificultad de resolver sistemas de ecuaciones polinómicas multivariables sobre campos finitos, un problema que se considera difícil incluso para computadoras cuánticas.

Fundamentos de Sistemas Polinómicos Multivariables

• Sistema Polinómico Multivariable: Conjunto de ecuaciones polinómicas con múltiples variables.
• Grado: El grado máximo de los polinomios en el sistema.
• Campo Base: Campo finito sobre el que se definen los polinomios (típicamente F₂ o campos pequeños).

Problemas Computacionales Multivariables

• Problema MQ (Multivariate Quadratic): Resolver un sistema de ecuaciones cuadráticas multivariables sobre un campo finito.
• Problema de Isomorfismo de Polinomios (IP): Determinar si dos conjuntos de polinomios son equivalentes bajo transformaciones lineales.
• Problema MinRank: Encontrar una combinación lineal de matrices con rango mínimo.

Algoritmos Basados en Sistemas Multivariables

• Rainbow: Esquema de firma basado en el principio de "aceite y vinagre", fue un finalista en el proceso del NIST pero se rompió en 2022.
• HFE (Hidden Field Equations): Utiliza polinomios simples en una extensión de campo que se vuelven complejos cuando se expresan sobre el campo base.
• UOV (Unbalanced Oil and Vinegar): Divide las variables en dos conjuntos ("aceite" y "vinagre") con interacciones específicas.
• MQDSS (Multivariate Quadratic Digital Signature Scheme): Esquema de firma basado directamente en el problema MQ.

Ventajas y Desventajas

Ventajas:

• Operaciones de verificación muy rápidas (especialmente útil para firmas).
• Basados en problemas bien estudiados en matemáticas computacionales.
• Estructura matemática diferente a otras familias post-cuánticas (diversificación).

Desventajas:

• Claves públicas grandes.
• Historial de esquemas rotos debido a estructura oculta.
• Complejidad en el diseño e implementación.

Estado Actual

La criptografía multivariable ha enfrentado desafíos significativos en los últimos años. Rainbow, que era un finalista en el proceso del NIST, fue roto en 2022. Sin embargo, la investigación continúa en nuevos diseños y variantes que podrían superar las vulnerabilidades identificadas.

3.6 Criptografía Basada en Hash

La criptografía basada en hash utiliza las propiedades de las funciones hash criptográficas para construir esquemas de firma digital resistentes a ataques cuánticos. Es una aproximación conceptualmente simple pero con implementaciones sofisticadas.

Fundamentos de Funciones Hash Criptográficas

• Función Hash: Mapea datos de tamaño arbitrario a valores de tamaño fijo.
• Propiedades Criptográficas: Resistencia a preimagen, a segunda preimagen y a colisiones.
• Funciones Hash Comunes: SHA-2, SHA-3, BLAKE2, BLAKE3.

Esquemas de Firma Basados en Hash

• Firmas de Un Solo Uso (OTS): Esquemas que solo pueden firmar un mensaje de forma segura.
  • Lamport-Diffie: Esquema básico de firma de un solo uso.
  • Winternitz OTS (WOTS): Mejora de Lamport-Diffie con firmas más compactas.
• Árboles de Merkle: Estructura que permite convertir esquemas de un solo uso en esquemas de múltiples usos.
  • XMSS (eXtended Merkle Signature Scheme): Esquema estandarizado por el IETF (RFC 8391).
  • SPHINCS: Esquema sin estado basado en árboles de hash hiperarbóreos.
• SLH-DSA (SPHINCS+): Versión mejorada de SPHINCS, seleccionada por el NIST para estandarización (FIPS 205).

Ventajas y Desventajas

Ventajas:

• Seguridad basada en propiedades fundamentales de funciones hash.
• Mínimas suposiciones criptográficas (solo requiere funciones hash seguras).
• Resistencia a avances en criptoanálisis cuántico y clásico.

Desventajas:

• Firmas relativamente grandes.
• Operaciones de firma y verificación más lentas que en otros esquemas.
• Complejidad en la implementación de árboles de Merkle eficientes.

3.7 Comparación de Enfoques Post-Cuánticos

Cada familia de algoritmos post-cuánticos tiene sus propias ventajas y desventajas en términos de seguridad, rendimiento y características prácticas.

Comparación de Rendimiento

Familia	Tamaño de Clave Pública	Tamaño de Firma/Cifrado	Velocidad de Operación
Retículos (ML-KEM)	Medio (~1-2 KB)	Pequeño-Medio (~1 KB)	Rápida
Retículos (ML-DSA)	Medio (~1-2 KB)	Medio (~2-3 KB)	Rápida
Códigos (Classic McEliece)	Muy grande (~1 MB)	Pequeño	Rápida (cifrado), Lenta (descifrado)
Isogenias (CSIDH)	Muy pequeño (~100 bytes)	Pequeño	Muy lenta
Multivariable	Grande (~100 KB)	Muy pequeño	Muy rápida (verificación), Media (firma)
Hash (SLH-DSA)	Pequeño (~32 bytes)	Grande (~8-30 KB)	Lenta

Comparación de Seguridad

Familia	Madurez del Análisis	Confianza en Suposiciones	Resistencia a Avances Criptanalíticos
Retículos	Alta	Media-Alta	Media-Alta
Códigos	Muy Alta	Alta	Alta
Isogenias	Baja-Media	Media	Media (algunos esquemas rotos)
Multivariable	Alta	Media-Baja	Baja (varios esquemas rotos)
Hash	Alta	Muy Alta	Muy Alta

Aplicaciones Recomendadas

• Retículos (ML-KEM, ML-DSA): Uso general para cifrado y firmas, buen equilibrio entre rendimiento y seguridad.
• Códigos (Classic McEliece): Aplicaciones de alta seguridad donde el tamaño de clave no es crítico.
• Hash (SLH-DSA): Aplicaciones que requieren garantías de seguridad máximas y pueden tolerar firmas grandes.
• Enfoque Híbrido: Combinar múltiples familias para diversificar las suposiciones de seguridad.