CSIDH: Isogenias Supersingulares Comutativas

CSIDH (Diffie-Hellman comutativo de isogenias supersingulares, Castryck et al., 2018) é uma troca de chaves baseada em isogenias que evita completamente o vazamento de pontos de torção do SIDH usando uma estrutura algébrica fundamentalmente diferente. O CSIDH trabalha com curvas supersingulares sobre Fp (não Fp2, como no SIDH). A hipótese de dificuldade é a comutatividade da ação do grupo de classes: cada uma das duas partes aplica um elemento secreto do grupo de classes a uma curva inicial comum, e a comutatividade garante que ambas cheguem à mesma curva compartilhada. Nenhuma informação auxiliar de pontos de torção é publicada — a chave pública é apenas um único invariante j. Esse projeto resistiu ao ataque de Castryck-Decru contra o SIDH.

Sobre Fp, com p = 3 mod 4, as curvas supersingulares E têm um endomorfismo distinguido pi (o Frobenius), e sua álgebra de endomorfismos contém a ordem quadrática imaginária Z[pi]. O grupo de classes de ideais Cl(Z[pi]) age livre e transitivamente sobre o conjunto de curvas supersingulares sobre Fp (a menos de isomorfismo). Um ideal a em Cl(Z[pi]) age sobre uma curva E para produzir uma nova curva a * E, calculada como a curva E/E[a], em que E[a] é o subgrupo de torção correspondente ao ideal a. Essa ação é comutativa: a * (b * E) = b * (a * E) = [ab] * E. Essa é a ação de grupo do CSIDH, que fornece um análogo comutativo do Diffie-Hellman.

A troca de chaves do CSIDH funciona da seguinte forma. Parâmetros públicos: uma curva supersingular E0 sobre Fp e primos ímpares pequenos l_1, ..., l_n. Chaves secretas: Alice escolhe a = (a_1, ..., a_n), em que cada a_i pertence a {-m, ..., m} (inteiros pequenos aleatórios). Bob escolhe b = (b_1, ..., b_n). Chave pública de Alice: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Chave pública de Bob: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Segredo compartilhado: Alice aplica seus expoentes secretos a E_B; Bob aplica os dele a E_A. A comutatividade garante que ambos obtenham E_AB = [produto(l_i^(a_i + b_i))] * E0. O segredo compartilhado é j(E_AB). Nenhum ponto auxiliar é publicado.

A implementação de referência do CSIDH usa p = 4 * l_1 * l_2 * ... * l_74 - 1, em que l_1 até l_74 são os primeiros 74 primos ímpares (3, 5, 7, ..., 373). Isso produz um p de aproximadamente 512 bits. Cada componente da chave secreta a_i pertence a {-5, ..., 5} (11 opções por componente, 74 componentes). A ordem do grupo de classes é aproximadamente sqrt(p), e o espaço de chaves tem tamanho 11^74. Para calcular cada etapa da isogenia: para cada primo l_i, encontre o subgrupo de torção l_i e calcule a l_i-isogenia usando as fórmulas de Velu. Com sqrt-Velu, cada etapa de isogenia para um primo grande requer O(sqrt(l_i)) operações. A troca de chaves completa leva aproximadamente de 1 a 5 ms em hardware moderno para o CSIDH-512.

O CSIDH original não executa em tempo constante: o número de etapas de Velu depende dos valores da chave secreta a_i, vazando informações por canais laterais de temporização. O CTIDH (Diffie-Hellman de ISOGENY em tempo constante, Bernstein et al., 2021) corrige isso usando um formato de chave de peso fixo e um cálculo de isogenias em tempo constante cuidadosamente projetado. As chaves secretas do CTIDH são restritas a vetores nos quais a soma dos valores absolutos é fixa (por exemplo, soma |a_i| = 130). O cálculo da isogenia prossegue por um número fixo de etapas, independentemente dos valores da chave secreta, usando cálculos fictícios de isogenias para preencher as etapas nas quais o expoente secreto é zero. O CTIDH alcança segurança semelhante à do CSIDH-512, com garantias rigorosas de tempo constante adequadas a implantações em sistemas embarcados.

A segurança quântica do CSIDH é mais complexa do que a dos esquemas baseados em reticulados. O melhor ataque quântico usa o algoritmo de Kuperberg (2005) para o problema do deslocamento oculto, que quebra a estrutura da ação do grupo de classes em tempo subexponencial L(1/2) = exp(O(sqrt(log p))). Isso é substancialmente melhor do que o melhor ataque clássico, de complexidade sqrt(p), o que significa que os computadores quânticos enfraquecem significativamente o CSIDH em comparação com os atacantes clássicos. Para obter segurança pós-quântica de 128 bits (contra um ataque L(1/2)), o CSIDH exige um primo p de aproximadamente 5000 bits (CSIDH-5000) — em comparação com 512 bits para obter segurança clássica de 128 bits. Estima-se que o CSIDH-512 ofereça apenas 62–72 bits de segurança quântica, muito abaixo dos requisitos do Nível 1 do NIST.

A segurança do CSIDH depende do Problema Inverso da Ação de Grupo (GAIP): dados E_A = a * E0 e E0, encontre a. O melhor algoritmo conhecido é uma redução semelhante à de Pohlig-Hellman combinada com o método do passo de bebê e passo de gigante, executada classicamente em O(sqrt(|Cl|)) ~ O(p^{1/4}). A dificuldade quântica (Kuperberg) torna o CSIDH menos seguro contra ataques quânticos do que os esquemas baseados em LWE. O melhor ataque quântico contra o LWE (a peneiração de reticulados) oferece margens de segurança mais conservadoras. A vantagem do CSIDH é seu tamanho compacto: o CSIDH-512 tem chaves públicas de 64 bytes (apenas o j-invariante), contra 800 bytes do ML-KEM-512. Para aplicações que exigem as menores chaves possíveis e aceitam margens de segurança quântica menores, o CSIDH continua interessante.

Várias variantes do CSIDH abordam suas limitações de segurança quântica. O BSIDH (B de “melhor”) usa curvas base de grau maior e produtos de curvas elípticas para aumentar o tamanho do grupo de classes, mantendo a computação rápida. O Csurf (CSIDH na superfície) trabalha com um conjunto diferente de curvas supersingulares para permitir uma computação mais rápida da ação de grupo. As propostas de CSIDH de gênero superior usam jacobianas de curvas de gênero 2 sobre Fp, oferecendo um espaço de ação de grupo maior, com margens de segurança quântica potencialmente melhores. Nenhuma dessas variantes alcançou adoção ampla ou foi considerada pelo NIST, em parte porque a análise da segurança quântica das variantes do CSIDH ainda está evoluindo e é menos madura do que a dos esquemas baseados em reticulados.

CSIDH e SIDH diferem de maneiras fundamentais. Comutatividade: o CSIDH usa uma ação de grupo comutativa (grupo de classes); o SIDH é uma troca de chaves não interativa que usa isogenias não comutativas com pontos de torção auxiliares. Corpo base: o CSIDH funciona sobre Fp; o SIDH, sobre Fp2 (extensão quadrática). Tamanho da chave pública: o CSIDH tem 64 bytes (um único j-invariante sobre Fp); o SIDH tem 324+ bytes (curva + dois pontos de Fp2). Segurança: o CSIDH resistiu ao ataque de Castryck-Decru; o SIDH foi quebrado. Segurança quântica: o CSIDH exige primos de 5000 bits para obter segurança quântica de 128 bits; o SIDH tinha resistência quântica comparável antes da quebra clássica. Desempenho: o CSIDH-512 leva aproximadamente 1–5 ms; o SIDH tinha desempenho semelhante, mas o CSIDH-5000 seria muito mais lento.

A comutatividade do CSIDH permite a troca de chaves não interativa (NIKE): Alice publica E_A = a * E0; Bob publica E_B = b * E0. Mais tarde, sem qualquer comunicação adicional, qualquer pessoa pode calcular o segredo compartilhado a partir de qualquer uma das chaves públicas: Alice calcula a * E_B = a * (b * E0) = ab * E0; Bob calcula b * E_A = b * (a * E0) = ab * E0. Essa propriedade de NIKE é valiosa para aplicações nas quais a troca de chaves interativa é impraticável — por exemplo, na cifragem de e-mails, quando o remetente e o destinatário não estão on-line simultaneamente. A NIKE do CSIDH é análoga à NIKE de Diffie-Hellman, mas pós-quântica. O ML-KEM (baseado em LWE) não oferece suporte natural à NIKE sem um projeto adicional de protocolo.

O CSIDH não foi padronizado e ainda não foi implantado em sistemas de produção. Ele é um tema ativo de pesquisa, com implementações disponíveis: CTIDH (tempo constante), csidh-reference (Python, para fins didáticos) e supersingular-isogeny-toolbox (C otimizado). O principal obstáculo à implantação é a segurança quântica: estima-se que os 62–72 bits de segurança quântica do CSIDH-512 fiquem abaixo do Nível 1 do NIST (128 bits), o que o torna inadequado para aplicações pós-quânticas que exigem conformidade com o NIST. O CSIDH-5000 atingiria o patamar de segurança necessário, mas seria drasticamente mais lento. A pesquisa continua concentrada no aprimoramento da análise da segurança quântica e em variantes que reduzam essa diferença, mas, em 2024, o CSIDH continua sendo um protótipo de pesquisa, e não uma primitiva pronta para implantação.

Por que a ação comutativa do grupo de classes do CSIDH permite a troca de chaves não interativa?

O CSIDH usa a ação comutativa do grupo de classes de Cl(Z[pi]) sobre curvas supersingulares sobre Fp, onde pi é o endomorfismo de Frobenius. As chaves públicas são j-invariantes únicos (64 bytes). Nenhum ponto de torção auxiliar é publicado, evitando a vulnerabilidade do SIDH. A ação do grupo de classes é comutativa, o que permite a NIKE. O melhor ataque clássico tem complexidade O(p^{1/4}); o melhor ataque quântico (Kuperberg) é executado em tempo subexponencial L(1/2), exigindo primos de 5000 bits para obter segurança quântica de 128 bits. O CTIDH fornece uma implementação em tempo constante. O CSIDH-512 oferece apenas aproximadamente 65 bits de segurança quântica. O CSIDH não foi padronizado; a pesquisa se concentra em variantes que melhorem a resistência quântica mantendo chaves compactas.