El futuro de la criptografía basada en isogenias

La ruptura de SIKE por Castryck-Decru en julio de 2022 cambió radicalmente el campo de la criptografía basada en isogenias. Antes de la ruptura, la criptografía basada en isogenias era una dirección poscuántica prometedora, con tamaños de clave reducidos, iniciativas activas de estandarización y una comunidad en crecimiento. Tras la caída de SIKE, el campo tuvo que reexaminar sus fundamentos. La pregunta clave es: ¿qué aspectos de la criptografía basada en isogenias siguen siendo difíciles después de las nuevas técnicas de isogenias de Richelot? La respuesta parece ser que la dificultad basada en anillos de endomorfismos (utilizada en SQISign) y las acciones conmutativas de grupos de clases (CSIDH) permanecen intactas. El componente vulnerado es la filtración de puntos de torsión auxiliares específica de SIDH, no las isogenias en general.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) es el esquema de firma poscuántica conocido más compacto. Clave pública: 64 bytes (un j-invariant supersingular). Firma: 177 bytes en el nivel 1. Como comparación, ML-DSA (Dilithium) tiene claves públicas de 1312 bytes y firmas de 2420 bytes en el nivel 2. La seguridad de SQISign se basa en la correspondencia de Deuring: el problema de calcular una isogenia de grado especificado entre dos curvas supersingulares dadas equivale a encontrar un ideal en el álgebra de cuaterniones del anillo de endomorfismos. SQISign utiliza un esquema de identificación Fiat-Shamir sobre este problema difícil y produce una firma como representación comprimida de la isogenia de respuesta.

La compacidad de SQISign implica un coste de rendimiento considerable. Para firmar, es necesario calcular una isogenia de grado grande (aproximadamente p^{1/4}) mediante la traducción de ideal a isogenia en el álgebra de cuaterniones, una operación de gran intensidad computacional que tarda aproximadamente entre 60 y 600 segundos en una CPU de escritorio, según el conjunto de parámetros. La verificación es más rápida (alrededor de 200 ms), pero sigue siendo mucho más lenta que la verificación de ML-DSA (microsegundos). SQISign 2.0 (2023) mejoró el rendimiento 100 veces mediante mejoras algorítmicas, reduciendo el tiempo de firma a entre 1 y 10 segundos. SQISign HD (high degree) y otras variantes siguen optimizándose. Su aplicación objetivo son los casos de uso en los que el ancho de banda está muy limitado (certificados de IoT, datos de blockchain y comunicaciones espaciales) y la velocidad de cálculo es secundaria.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) es un KEM diseñado explícitamente para evitar la filtración de puntos de torsión al estilo de SIDH. Su idea de diseño clave consiste en que, en lugar de publicar phi_A(P_B) y phi_A(Q_B) como en SIDH, FESTA utiliza una estructura de isogenia diferente en la que la clave pública del cifrador es únicamente la curva imagen (sin imágenes de torsión). FESTA utiliza isogenias 2^n de una manera modificada que permite descifrar sin las imágenes de la base de torsión de la otra parte. Los primeros análisis sugieren que FESTA resiste el ataque de Castryck-Decru debido a su estructura diferente de información auxiliar. FESTA es una dirección prometedora, pero requiere un análisis criptográfico más exhaustivo; la comunidad de las isogenias mantiene la cautela después de la inesperada ruptura de SIKE.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) aborda la debilidad de seguridad cuántica de CSIDH. El primo pequeño p = 512 bits de CSIDH proporciona solo unos 65 bits de seguridad cuántica (debido al algoritmo subexponencial de Kuperberg). SCALLOP utiliza una estructura algebraica diferente: curvas con multiplicación compleja por órdenes cuadráticos imaginarios grandes, cuyo grupo de clases está diseñado específicamente para resistir los ataques cuánticos al estilo de Kuperberg. SCALLOP consigue un grupo de clases efectivo mayor, con parámetros que proporcionan una seguridad cuántica de 128 bits usando tamaños de parámetros menores que CSIDH-5000. La contrapartida es que la configuración algebraica de SCALLOP es más compleja y ha recibido menos análisis independiente que CSIDH.

Dada la compacidad excepcional de los esquemas basados en isogenias (firmas de 177 bytes en SQISign y claves de 64 bytes en CSIDH) y sus supuestos de dificultad distintos de los de los esquemas basados en retículos, las construcciones híbridas combinan componentes basados en isogenias y en retículos para proporcionar una defensa en profundidad. En un KEM híbrido, se encapsula tanto con ML-KEM-512 COMO con CSIDH-512 y se calculan ambos secretos conjuntamente mediante una función hash. Para romper la clave combinada sería necesario vulnerar simultáneamente ML-KEM (la dificultad de LWE) y CSIDH (la acción del grupo de clases). Si uno de los dos permanece sin vulnerar, el esquema híbrido es seguro. NIST y NSA recomiendan este enfoque de agilidad criptográfica a las organizaciones que desean garantías adicionales más allá de cualquier primitiva poscuántica individual, especialmente cuando no está claro el plazo para disponer de ordenadores cuánticos.

Las pruebas de conocimiento cero basadas en isogenias son una línea de investigación emergente. El problema del camino de isogenias (encontrar phi: E -> E' dadas ambas curvas) puede servir como problema difícil para esquemas de prueba de conocimiento. Los protocolos Sigma para demostrar "conozco una isogenia de E a E'" permiten la autenticación sin revelar la isogenia. Vero (2022) demuestra un sistema práctico de pruebas de conocimiento cero basado en isogenias. Estas pruebas de conocimiento cero son naturalmente compactas (el enunciado consta únicamente de dos j-invariants), pero actualmente son demasiado lentas para su implementación práctica. A medida que mejore el cálculo de isogenias, las pruebas de conocimiento cero basadas en isogenias podrían ofrecer alternativas a las pruebas basadas en retículos o funciones hash cuando se valore la diversidad de supuestos.

Las técnicas de isogenias no solo son relevantes para la criptografía poscuántica; también tienen aplicaciones en la criptografía clásica de curvas elípticas. El algoritmo de Schoof-Elkies-Atkin (SEA) para contar puntos en curvas elípticas utiliza isogenias para calcular la traza de Frobenius, lo que permite generar de forma eficiente parámetros seguros para curvas elípticas. Las isogenias aparecen en mejoras del algoritmo rho de Pollard para calcular el ECDLP. El método CM (Complex Multiplication) para construir curvas de orden prefijado utiliza polinomios de clases que son, fundamentalmente, objetos relacionados con isogenias. Las herramientas de criptoanálisis basadas en isogenias (para encontrar caminos de isogenias de grado suave) se utilizan para evaluar parámetros de curvas elípticas propuestos en busca de puertas traseras ocultas, una cuestión directamente relacionada con el problema de Dual EC DRBG.

A fecha de 2024, ningún esquema basado en isogenias ha sido estandarizado por NIST ni por otros organismos importantes. El proceso PQC de NIST estandarizó ML-KEM, ML-DSA, SLH-DSA y FN-DSA, todos ellos basados en retículos o funciones hash. NIST está llevando a cabo una segunda ronda de evaluación de firmas PQC; SQISign fue presentado, pero afronta problemas de rendimiento. La comunidad de las isogenias trabaja para desarrollar una versión más madura, SQISign 3.0, con tiempos de firma prácticos (con el objetivo de bajar de un segundo). ISO y ETSI no han estandarizado ningún esquema basado en isogenias. La vía de estandarización más probable a corto plazo es SQISign para aplicaciones especializadas que requieran tamaños de firma mínimos, posiblemente como estándar informativo en lugar de como primitiva obligatoria. Para lograr una implementación generalizada se necesitan mejoras de rendimiento de varios órdenes de magnitud.

Direcciones activas de investigación en criptografía basada en isogenias a fecha de 2024: (1) variantes de SQISign (SQISign 2.0, HD, Fast SQISign) que mejoran el rendimiento de firma para acercarlo a una operación de menos de un segundo. (2) Análisis de la seguridad cuántica de CSIDH y sus variantes: perfeccionamiento de las estimaciones de los ataques de Kuperberg y exploración de estructuras algebraicas que los resistan. (3) Nuevos supuestos de dificultad: cálculo de anillos de endomorfismos supersingulares y problemas de módulos sobre anillos cuadráticos imaginarios. (4) PRF oblivious basadas en isogenias y aplicaciones a protocolos que preservan la privacidad. (5) Implementaciones hardware de aritmética de isogenias, aprovechando el paralelismo de las FPGA para la acción del grupo de clases de CSIDH. (6) Integración de acciones de grupo basadas en isogenias con marcos de criptografía de acción de grupo genérica para crear nuevos esquemas de cifrado funcional y basados en atributos.

El ataque contra SIKE podría sugerir abandonar por completo la criptografía basada en isogenias. La comunidad criptográfica adopta el punto de vista opuesto: el ataque fue valioso precisamente porque permitió identificar qué estructuras no son seguras (la filtración de puntos de torsión de SIDH) y cuáles siguen siendo difíciles de resolver (los anillos de endomorfismos y las acciones de grupos de clases). Estudiar las isogenias sigue siendo importante por varias razones: (1) diversidad poscuántica: contar con supuestos de seguridad distintos de los basados en retículos reduce el riesgo sistémico si se rompe LWE; (2) SQISign ofrece firmas excepcionalmente compactas, sin competidores actuales; (3) las técnicas de isogenias aportan conocimientos útiles para el criptoanálisis de curvas elípticas y la validación de parámetros; (4) las matemáticas son elegantes y productivas: las herramientas desarrolladas para atacar SIKE mejoraron directamente la comprensión de los anillos de endomorfismos de curvas elípticas utilizados en otros contextos.

¿Qué supuesto de dificultad sustenta las firmas de SQISign?

Tras el ataque de 2022 contra SIKE, la criptografía basada en isogenias continúa mediante distintos supuestos de dificultad. SQISign ofrece firmas poscuánticas de 177 bytes (las más pequeñas conocidas), basadas en la dificultad de los anillos de endomorfismos; su rendimiento está mejorando (con el objetivo de bajar de un segundo). FESTA se diseña para evitar la filtración de puntos de torsión de SIDH en los KEM. SCALLOP busca alcanzar una seguridad cuántica de 128 bits mediante curvas orientadas. Los esquemas híbridos de isogenias y retículos ofrecen diversidad de supuestos. Actualmente no hay ningún esquema basado en isogenias estandarizado. La estandarización de SQISign es la vía más probable a corto plazo. El ataque contra SIKE permitió comprender mejor qué elementos deben mantenerse ocultos en los protocolos basados en isogenias y produjo nuevas herramientas matemáticas utilizadas en toda la criptografía de curvas elípticas.