Isogenias de curvas elípticas: fundamentos matemáticos

Una isogenia entre dos curvas elípticas E y E' sobre un cuerpo k es un mapa racional no constante phi: E -> E' que también es un homomorfismo de grupos: transforma la ley de grupo de E en la ley de grupo de E'. Toda isogenia phi tiene una isogenia dual phi_hat: E' -> E, de modo que phi_hat compuesta con phi es igual a la multiplicación por deg(phi) en E. El grado de una isogenia es el tamaño de su núcleo: una isogenia de grado l tiene un núcleo de tamaño l. Las isogenias generalizan la multiplicación por escalares: la multiplicación por n es una isogenia de E en sí misma de grado n^2. Las isogenias sobre cuerpos finitos se calculan como funciones racionales (polinomios) que pueden evaluarse eficientemente.

Las fórmulas de Velu (1971) proporcionan fórmulas explícitas para calcular una isogenia phi: E -> E/G dado un subgrupo G de E. La curva imagen E/G = E' y el mapa racional phi están completamente determinados por G. Las fórmulas de Velu calculan los coeficientes de la curva imagen y el mapa racional como funciones racionales de grado igual a |G|. Para un subgrupo núcleo G de orden primo l, la isogenia tiene grado l y puede calcularse en O(l) operaciones. Los algoritmos sqrt-Velu (Bernstein et al., 2019) reducen este coste a O(sqrt(l)) operaciones para valores grandes de l, lo que permite las isogenias eficientes de primos grandes de CSIDH. Las fórmulas de Velu son el principal motor computacional de toda la criptografía basada en isogenias.

Las curvas elípticas sobre un cuerpo finito Fp pueden organizarse en un grafo de isogenias. Los vértices son invariantes j de curvas elípticas (un invariante canónico que determina la curva salvo isomorfismo). Las aristas son isogenias de grado l: cada curva ordinaria tiene exactamente l+1 isogenias de grado l salientes para un primo l pequeño (por la estructura de los subgrupos de l-torsión). El grafo de isogenias de grado l sobre Fp es un grafo (l+1)-regular. La propiedad de Ramanujan de estos grafos (grafos expansores) hace que las caminatas aleatorias se mezclen rápidamente, lo que proporciona el supuesto de dificultad en el que se basa la criptografía basada en isogenias: las caminatas aleatorias de longitud O(log p) producen distribuciones uniformes sobre los invariantes j.

Las curvas elípticas sobre Fp se dividen en dos categorías. Las curvas ordinarias tienen un rango p no trivial, lo que significa que existen p^2 clases de isomorfismo y un grafo de isogenias complejo con una estructura de volcán (cráteres y niveles). Las curvas supersingulares tienen rango p igual a 0 y todas pertenecen a un único grafo de isogenias conexo sobre Fp2. El número de invariantes j supersingulares sobre Fp es aproximadamente p/12. SIDH y SIKE utilizan curvas supersingulares porque su grafo de isogenias es un grafo de Ramanujan con sólidas propiedades expansoras y sin una estructura de volcán que pueda revelar la dirección de la caminata. CSIDH también utiliza curvas supersingulares, pero sobre Fp (no sobre Fp2), aprovechando una estructura algebraica diferente.

La criptografía basada en isogenias se fundamenta en dos problemas difíciles relacionados. Problema de isogenias supersingulares (SSIP): dadas dos curvas elípticas supersingulares E y E' sobre Fp2, encontrar una isogenia phi: E -> E'. Problema de isogenias supersingulares computacionales (CSSI): dados E, E' = phi(E) y el grado de phi, encontrar phi. El mejor algoritmo clásico para SSIP se ejecuta en tiempo O(p^{1/4}). El mejor algoritmo cuántico (búsqueda de colisiones de Tani) se ejecuta en O(p^{1/6}). Para p = 2^{434}, esto proporciona una seguridad clásica de 128 bits. Estas aceleraciones cuánticas son considerablemente menores que la aceleración exponencial del algoritmo de Shor contra RSA/ECC, por lo que los esquemas basados en isogenias son poscuánticos.

SIDH (Supersingular Isogeny Diffie-Hellman) utiliza un primo con una estructura especial p = 2^a * 3^b - 1 que garantiza que la curva E sobre Fp2 tenga puntos de 2^a-torsión (el conjunto de puntos P para los que 2^a * P = 0) y puntos de 3^b-torsión accesibles. El secreto de Alice es una isogenia de grado 2^a phi_A: E -> E_A cuyo núcleo está generado por un elemento aleatorio de la 2^a-torsión. El secreto de Bob es una isogenia de grado 3^b phi_B: E -> E_B. Intercambian imágenes de puntos de torsión: Alice publica E_A y phi_A(P_B), phi_A(Q_B). Bob publica E_B y phi_B(P_A), phi_B(Q_A). Esto permite que cada parte calcule isogenias a partir de la curva de la otra y llegue al mismo invariante j compartido.

El anillo de endomorfismos End(E) de una curva elíptica es el anillo de todas las isogenias de E en sí misma (incluidas las multiplicaciones por escalares). Para las curvas ordinarias sobre Fp, End(E) es un orden en un cuerpo cuadrático imaginario. Para las curvas supersingulares, End(E) es un orden maximal en un álgebra de cuaterniones ramificada en p y en el infinito. La estructura de End(E) determina por completo la curva salvo isomorfismo. Se cree que el problema del anillo de endomorfismos —calcular End(E) a partir de E— es difícil (equivalente a SSIP para las curvas supersingulares). El ataque de Castryck-Decru contra SIDH/SIKE aprovechó información adicional filtrada por el protocolo SIDH para reconstruir eficientemente parte del anillo de endomorfismos y romper el esquema.

Una isogenia de grado l phi: E -> E' puede representarse como un polinomio de grado l (o l/2 después de optimizar mediante simetría, aprovechando que los puntos inversos tienen la misma coordenada x). Calcular phi(P) para un punto P dado requiere O(l) multiplicaciones mediante las fórmulas de Velu. Para SIDH, con l = 2^a alrededor de 2^216, esto parece prohibitivo, pero SIDH aprovecha que las isogenias de grado 2^a pueden descomponerse en una cadena de a isogenias individuales de grado 2: cada isogenia de grado 2 es barata y una cadena de a pasos produce una isogenia de grado 2^a. Lo mismo ocurre con 3^b. sqrt-Velu permite ejecutar los cálculos de isogenias de primos impares grandes de CSIDH en O(sqrt(l)) en lugar de O(l), lo que hace práctico CSIDH.

SIKE (Supersingular Isogeny Key Encapsulation) fue un candidato de la competición PQC de NIST que superó todas las rondas hasta la cuarta, cuando fue vulnerado. SIKE destacaba por tener los tamaños de clave más pequeños de todos los candidatos de NIST: 374 bytes para SIKEp434 (nivel 1 de NIST). A modo de comparación, las claves públicas de ML-KEM-512 tienen 800 bytes. SIKE lograba este tamaño compacto porque el secreto compartido se deriva de un único invariante j (un elemento del cuerpo de aproximadamente 430 bits). Esta compacidad tenía un coste: SIKE era entre 100 y 1000 veces más lento que los demás candidatos. Cuando Castryck y Decru vulneraron SIKE en julio de 2022 mediante un ataque clásico que se ejecutaba en minutos en un portátil, SIKE fue eliminado inmediatamente de la competición de NIST.

La criptografía basada en isogenias ocupa una posición única entre los enfoques poscuánticos. Tamaños de clave: mucho menores que los de la criptografía basada en retículas (ML-KEM: más de 800 bytes) o las firmas basadas en funciones hash (SLH-DSA: clave pública de 32-49 bytes, pero firmas de 7856-49856 bytes). Rendimiento: mucho más lento que todas las alternativas (SIKE era entre 100 y 1000 veces más lento que ML-KEM). Supuesto de seguridad: distinto de LWE (utilizado en ML-KEM/ML-DSA), SIS o las funciones hash, lo que proporciona diversidad criptográfica. Base de la seguridad poscuántica: el problema de la ruta de isogenias no cuenta con ningún algoritmo cuántico de tiempo polinómico conocido, a diferencia de RSA/ECC, que el algoritmo de Shor rompe por completo. El ataque clásico contra SIKE demuestra que la dificultad de las isogenias todavía se está estudiando, a diferencia del problema LWE, que ha sido estudiado exhaustivamente.

A pesar de la vulneración de SIKE, la criptografía basada en isogenias sigue siendo un área de investigación activa. SQISign (Short Quaternion and Isogeny Signature) es un esquema de firma basado en isogenias con firmas de 177 bytes (frente a los 2420 bytes de ML-DSA para el nivel 2), las firmas PQC más pequeñas conocidas. SQISign utiliza el problema difícil de calcular una isogenia de grado prescrito entre dos curvas supersingulares dadas, formalizado como el problema del anillo de endomorfismos. FESTA (Fast Encryption from Supersingular Torsion Attacks) es un nuevo diseño de KEM que evita los datos auxiliares adicionales de puntos de torsión que hicieron vulnerable a SIDH. CTIDH (Constant-Time CSIDH) mejora el rendimiento de CSIDH. Estos esquemas mantienen la relevancia de la investigación sobre isogenias incluso después de la eliminación de SIKE.

¿Qué es una isogenia entre curvas elípticas?

Una isogenia es un mapa racional phi: E -> E' que es un homomorfismo de grupos y cuyo grado es igual al tamaño de su núcleo. Las fórmulas de Velu calculan la curva imagen y el mapa a partir del subgrupo núcleo. Los grafos de isogenias organizan las curvas como vértices con aristas de grado l que forman grafos de Ramanujan (l+1)-regulares. Las curvas supersingulares (utilizadas en SIDH/SIKE/CSIDH) tienen grafos de isogenias con una fuerte expansión. Los problemas SSIP y CSSI sustentan la seguridad de las isogenias. SIDH utiliza la estructura de los puntos de torsión con cadenas alternas de isogenias de grado 2 y 3. El cálculo del anillo de endomorfismos es equivalente a SSIP. SQISign y FESTA representan líneas activas de investigación posteriores a SIKE que utilizan la dificultad del anillo de endomorfismos.