CSIDH: isogenias supersingulares conmutativas

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck et al., 2018) es un intercambio de claves basado en isogenias que evita por completo la filtración de puntos de torsión de SIDH mediante una estructura algebraica fundamentalmente diferente. CSIDH trabaja con curvas supersingulares sobre Fp (no sobre Fp2, como SIDH). El supuesto de dificultad se basa en la conmutatividad de la acción del grupo de clases: cada una de las dos partes aplica un elemento secreto del grupo de clases a una curva inicial común, y la conmutatividad garantiza que ambas lleguen a la misma curva compartida. No se publica ninguna información auxiliar sobre puntos de torsión; la clave pública es únicamente un j-invariant. Este diseño sobrevivió al ataque de Castryck-Decru contra SIDH.

Sobre Fp con p = 3 mod 4, las curvas supersingulares E tienen un endomorfismo distinguido pi (el Frobenius), y su álgebra de endomorfismos contiene el orden cuadrático imaginario Z[pi]. El grupo de clases de ideales Cl(Z[pi]) actúa de forma libre y transitiva sobre el conjunto de curvas supersingulares sobre Fp (salvo isomorfismo). Un ideal a de Cl(Z[pi]) actúa sobre una curva E para producir una curva nueva a * E, calculada como la curva E/E[a], donde E[a] es el subgrupo de torsión correspondiente al ideal a. Esta acción es conmutativa: a * (b * E) = b * (a * E) = [ab] * E. Esta es la acción del grupo de CSIDH, que proporciona un análogo conmutativo de Diffie-Hellman.

El intercambio de claves CSIDH funciona de la siguiente manera. Parámetros públicos: una curva supersingular E0 sobre Fp y primos impares pequeños l_1, ..., l_n. Claves secretas: Alice elige a = (a_1, ..., a_n), donde cada a_i pertenece a {-m, ..., m} (enteros pequeños aleatorios). Bob elige b = (b_1, ..., b_n). Clave pública de Alice: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Clave pública de Bob: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Secreto compartido: Alice aplica sus exponentes secretos a E_B; Bob aplica los suyos a E_A. La conmutatividad garantiza que ambos obtengan E_AB = [product(l_i^(a_i + b_i))] * E0. El secreto compartido es j(E_AB). No se publican puntos auxiliares.

La implementación de referencia de CSIDH utiliza p = 4 * l_1 * l_2 * ... * l_74 - 1, donde l_1 a l_74 son los primeros 74 primos impares (3, 5, 7, ..., 373). Esto produce un valor de p de aproximadamente 512 bits. Cada componente de la clave secreta a_i pertenece a {-5, ..., 5} (11 opciones por componente y 74 componentes). El orden del grupo de clases es aproximadamente sqrt(p), y el espacio de claves tiene un tamaño de 11^74. Para calcular cada paso de isogenia, se busca el subgrupo de torsión l_i y se calcula la l_i-isogenia mediante las fórmulas de Velu. Con sqrt-Velu, cada paso de isogenia de primo grande requiere O(sqrt(l_i)) operaciones. El intercambio de claves completo tarda aproximadamente entre 1 y 5 ms en hardware moderno para CSIDH-512.

El CSIDH original no es de tiempo constante: el número de pasos de Velu depende de los valores de la clave secreta a_i, lo que filtra información a través de canales laterales temporales. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein et al., 2021) corrige este problema mediante un formato de clave de peso fijo y un cálculo de isogenias de tiempo constante diseñado cuidadosamente. Las claves secretas de CTIDH están restringidas a vectores cuya suma de valores absolutos es fija (por ejemplo, sum |a_i| = 130). El cálculo de la isogenia se realiza en un número fijo de pasos, independientemente de los valores de la clave secreta, utilizando cálculos de isogenias ficticios para completar los pasos en los que el exponente secreto es cero. CTIDH consigue una seguridad similar a la de CSIDH-512, con estrictas garantías de tiempo constante adecuadas para implementaciones en sistemas embebidos.

La seguridad cuántica de CSIDH es más matizada que la de los esquemas basados en retículos. El mejor ataque cuántico utiliza el algoritmo de Kuperberg (2005) para el problema del desplazamiento oculto, que vulnera la estructura de acción del grupo de clases en tiempo subexponencial L(1/2) = exp(O(sqrt(log p))). Esto es considerablemente mejor que el mejor ataque clásico, de complejidad sqrt(p), lo que significa que los ordenadores cuánticos debilitan significativamente CSIDH en comparación con los atacantes clásicos. Para alcanzar una seguridad poscuántica de 128 bits (frente a un ataque L(1/2)), CSIDH requiere un primo p de aproximadamente 5000 bits (CSIDH-5000), frente a los 512 bits necesarios para una seguridad clásica de 128 bits. Se estima que CSIDH-512 ofrece solo entre 62 y 72 bits de seguridad cuántica, muy por debajo de los requisitos del nivel 1 de NIST.

La seguridad de CSIDH se basa en el problema inverso de la acción de grupo (GAIP): dados E_A = a * E0 y E0, encontrar a. El algoritmo más eficiente conocido es una reducción similar a la de Pohlig-Hellman combinada con baby-step-giant-step, con una complejidad clásica de O(sqrt(|Cl|)) ~ O(p^{1/4}). La dificultad cuántica (Kuperberg) hace que CSIDH sea menos seguro frente a ataques cuánticos que los esquemas basados en LWE. El mejor ataque cuántico contra LWE (sieving de retículos) proporciona márgenes de seguridad más conservadores. La ventaja de CSIDH es su compacidad: CSIDH-512 tiene claves públicas de 64 bytes (solo el j-invariant), frente a los 800 bytes de ML-KEM-512. Para aplicaciones que requieren las claves más pequeñas posibles y aceptan márgenes de seguridad cuántica inferiores, CSIDH sigue siendo una opción interesante.

Varias variantes de CSIDH abordan sus limitaciones de seguridad cuántica. BSIDH (la B significa "better") utiliza curvas base de mayor grado y productos de curvas elípticas para aumentar el tamaño del grupo de clases y mantener la rapidez de cálculo. Csurf (CSIDH en la superficie) trabaja con un conjunto diferente de curvas supersingulares para permitir un cálculo más rápido de la acción de grupo. Las propuestas de CSIDH de género superior utilizan jacobianas de curvas de género 2 sobre Fp, lo que proporciona un espacio de acción de grupo mayor y, potencialmente, mejores márgenes de seguridad cuántica. Ninguna de estas variantes ha alcanzado una adopción generalizada ni ha sido considerada por NIST, en parte porque el análisis de la seguridad cuántica de las variantes de CSIDH todavía está evolucionando y es menos maduro que el de los esquemas basados en retículos.

CSIDH y SIDH difieren en aspectos fundamentales. Conmutatividad: CSIDH utiliza una acción de grupo conmutativa (el grupo de clases); SIDH es un intercambio de claves no interactivo basado en isogenias no conmutativas con puntos de torsión auxiliares. Campo base: CSIDH trabaja sobre Fp; SIDH, sobre Fp2 (una extensión cuadrática). Tamaño de la clave pública: CSIDH ocupa 64 bytes (un único j-invariant sobre Fp); SIDH ocupa más de 324 bytes (una curva y dos puntos de Fp2). Seguridad: CSIDH sobrevivió al ataque de Castryck-Decru; SIDH fue vulnerado. Seguridad cuántica: CSIDH requiere primos de 5000 bits para ofrecer una seguridad cuántica de 128 bits; SIDH tenía una resistencia cuántica comparable antes de la ruptura clásica. Rendimiento: CSIDH-512 tarda aproximadamente entre 1 y 5 ms; SIDH tenía un rendimiento similar, pero CSIDH-5000 sería mucho más lento.

La conmutatividad de CSIDH permite un intercambio de claves no interactivo (NIKE): Alice publica E_A = a * E0; Bob publica E_B = b * E0. Más tarde, sin ninguna comunicación adicional, cualquiera de los dos puede calcular el secreto compartido a partir de la clave pública del otro: Alice calcula a * E_B = a * (b * E0) = ab * E0; Bob calcula b * E_A = b * (a * E0) = ab * E0. Esta propiedad NIKE es valiosa para aplicaciones en las que un intercambio de claves interactivo resulta poco práctico; por ejemplo, para cifrar el correo electrónico cuando el remitente y el destinatario no están conectados simultáneamente. El NIKE de CSIDH es análogo al NIKE de Diffie-Hellman, pero poscuántico. ML-KEM (basado en LWE) no admite NIKE de forma natural sin un diseño de protocolo adicional.

CSIDH no se ha estandarizado y todavía no se ha implementado en sistemas de producción. Es un tema de investigación activo con varias implementaciones disponibles: CTIDH (de tiempo constante), csidh-reference (Python, con fines didácticos) y supersingular-isogeny-toolbox (C optimizado). La principal barrera para su implementación es la seguridad cuántica: se estima que los entre 62 y 72 bits de seguridad cuántica de CSIDH-512 están por debajo del nivel 1 de NIST (128 bits), por lo que no resulta adecuado para aplicaciones poscuánticas que requieran el cumplimiento de NIST. CSIDH-5000 alcanzaría el nivel de seguridad requerido, pero sería mucho más lento. La investigación continúa para mejorar el análisis de la seguridad cuántica y desarrollar variantes que cierren esta brecha, pero, a fecha de 2024, CSIDH sigue siendo un prototipo de investigación y no un mecanismo criptográfico listo para su implementación.

¿Por qué la acción conmutativa del grupo de clases de CSIDH permite realizar un intercambio de claves no interactivo?

CSIDH utiliza la acción conmutativa del grupo de clases de Cl(Z[pi]) sobre curvas supersingulares definidas sobre Fp, donde pi es el endomorfismo de Frobenius. Las claves públicas son j-invariants individuales (64 bytes). No se publican puntos de torsión auxiliares, por lo que se evita la vulnerabilidad de SIDH. La acción del grupo de clases es conmutativa, lo que permite NIKE. El mejor ataque clásico tiene una complejidad de O(p^{1/4}); el mejor ataque cuántico (Kuperberg) se ejecuta en tiempo subexponencial L(1/2), por lo que se necesitan primos de 5000 bits para alcanzar una seguridad cuántica de 128 bits. CTIDH proporciona una implementación de tiempo constante. CSIDH-512 ofrece solo unos 65 bits de seguridad cuántica. CSIDH no está estandarizado; la investigación se centra en variantes que mejoren la resistencia cuántica manteniendo unas claves compactas.