Isogenias de Curvas Elípticas: Fundamentos Matemáticos

Uma isogenia entre duas curvas elípticas E e E' sobre um corpo k é uma aplicação racional não constante phi: E -> E' que também é um homomorfismo de grupos — ela mapeia a lei de grupo de E para a lei de grupo de E'. Toda isogenia phi tem uma isogenia dual phi_hat: E' -> E tal que phi_hat composta com phi é igual à multiplicação por deg(phi) em E. O grau de uma isogenia é o tamanho de seu núcleo: uma isogenia de grau l tem um núcleo de tamanho l. Isogenias generalizam a multiplicação escalar: a multiplicação por n é uma isogenia de E em si mesmo de grau n^2. As isogenias sobre corpos finitos são calculadas como funções racionais (polinômios) que podem ser avaliadas com eficiência.

As fórmulas de Velu (1971) fornecem fórmulas explícitas para calcular uma isogenia phi: E -> E/G dado um subgrupo G de E. A curva imagem E/G = E' e a aplicação racional phi são completamente determinadas por G. As fórmulas de Velu calculam os coeficientes da curva imagem e a aplicação racional como funções racionais de grau igual a |G|. Para um subgrupo núcleo G de ordem prima l, a isogenia tem grau l e pode ser calculada em O(l) operações. Os algoritmos sqrt-Velu (Bernstein et al., 2019) reduzem isso a O(sqrt(l)) operações para l grande, permitindo as isogenias eficientes de primos grandes do CSIDH. As fórmulas de Velu são a principal ferramenta computacional de toda a criptografia baseada em isogenias.

Curvas elípticas sobre um corpo finito Fp podem ser organizadas em um grafo de isogenias. Os vértices são invariantes j de curvas elípticas (um invariante canônico que determina a curva até um isomorfismo). As arestas são isogenias de grau l: cada curva ordinária tem exatamente l+1 isogenias de grau l de saída para um primo pequeno l (pela estrutura dos subgrupos de l-torção). O grafo de isogenias de grau l sobre Fp é um grafo regular de grau l+1. A propriedade de Ramanujan desses grafos (grafos expansores) significa que passeios aleatórios neles se misturam rapidamente, fornecendo a hipótese de dificuldade subjacente à criptografia baseada em isogenias: passeios aleatórios de comprimento O(log p) produzem distribuições uniformes sobre invariantes j.

As curvas elípticas sobre Fp se dividem em duas categorias. As curvas ordinárias têm posto-p não trivial, o que significa que existem p^2 classes de isomorfismo e um grafo de isogenias complexo com uma estrutura de vulcão (crateras e pisos). As curvas supersingulares têm posto-p igual a 0 e todas vivem em um único grafo de isogenias conectado sobre Fp2. O número de invariantes j supersingulares sobre Fp é aproximadamente p/12. SIDH e SIKE usam curvas supersingulares porque seu grafo de isogenias é um grafo de Ramanujan com fortes propriedades de expansão e sem uma estrutura de vulcão que pudesse revelar a direção do passeio. CSIDH também usa curvas supersingulares, mas sobre Fp (não Fp2), explorando uma estrutura algébrica diferente.

A criptografia baseada em isogenias fundamenta-se em dois problemas difíceis relacionados. Problema da Isogenia Supersingular (SSIP): dadas duas curvas elípticas supersingulares E e E' sobre Fp2, encontre uma isogenia phi: E -> E'. Problema Computacional da Isogenia Supersingular (CSSI): dados E, E' = phi(E) e o grau de phi, encontre phi. O melhor algoritmo clássico para SSIP é executado em tempo O(p^{1/4}). O melhor algoritmo quântico (localização de garras de Tani) é executado em tempo O(p^{1/6}). Para p = 2^{434}, isso resulta em segurança clássica de 128 bits. Esses ganhos quânticos são significativamente menores que o ganho exponencial do algoritmo de Shor contra RSA/ECC, tornando os esquemas baseados em isogenias seguros no cenário pós-quântico.

SIDH (Diffie-Hellman de Isogenia Supersingular) usa um primo especialmente estruturado p = 2^a * 3^b - 1 que garante que a curva E sobre Fp2 tenha pontos de 2^a-torção (o conjunto de pontos P com 2^a * P = 0) e pontos de 3^b-torção acessíveis. O segredo de Alice é uma isogenia de 2^a phi_A: E -> E_A cujo núcleo é gerado por um elemento aleatório da 2^a-torção. O segredo de Bob é uma isogenia de 3^b phi_B: E -> E_B. Eles trocam imagens dos pontos de torção: Alice publica E_A e phi_A(P_B), phi_A(Q_B). Bob publica E_B e phi_B(P_A), phi_B(Q_A). Isso permite que cada parte calcule isogenias a partir da curva da outra, chegando ao mesmo invariante j compartilhado.

O anel de endomorfismos End(E) de uma curva elíptica é o anel de todas as isogenias de E em si mesma (incluindo multiplicações escalares). Para curvas ordinárias sobre Fp, End(E) é uma ordem em um corpo quadrático imaginário. Para curvas supersingulares, End(E) é uma ordem maximal em uma álgebra de quatérnios ramificada em p e no infinito. A estrutura de End(E) determina completamente a curva até um isomorfismo. Acredita-se que o problema do anel de endomorfismos — calcular End(E) dado E — seja difícil (equivalente ao SSIP para curvas supersingulares). O ataque de Castryck-Decru contra SIDH/SIKE explorou informações extras vazadas no protocolo SIDH para reconstruir eficientemente parte do anel de endomorfismos, quebrando o esquema.

Uma isogenia de grau l phi: E -> E' pode ser representada por um polinômio de grau l (ou l/2 após uma otimização por simetria, usando o fato de que pontos inversos têm a mesma coordenada x). Calcular phi(P) para um ponto P dado requer O(l) multiplicações usando as fórmulas de Velu. Para SIDH com l = 2^a em torno de 2^216, isso parece proibitivo, mas SIDH usa o fato de que as isogenias de 2^a podem ser decompostas em uma cadeia de a isogenias de grau 2 — cada isogenia de grau 2 é barata, e uma cadeia de a etapas produz uma isogenia de grau 2^a. O mesmo vale para 3^b. sqrt-Velu permite que os cálculos de isogenias de grandes primos ímpares do CSIDH sejam executados em O(sqrt(l)), em vez de O(l), tornando o CSIDH viável.

SIKE (Encapsulamento de Chaves por Isogenia Supersingular) foi um candidato à PQC da NIST que sobreviveu a todas as rodadas até a quarta, quando foi quebrado. O SIKE se destacou por ter os menores tamanhos de chave entre todos os candidatos da NIST: 374 octetos para SIKEp434 (Nível 1 da NIST). Para comparação, o ML-KEM-512 tem chaves públicas de 800 octetos. O SIKE alcançou essa compactação porque o segredo compartilhado deriva de um único invariante j (um elemento de corpo de aproximadamente 430 bits). A compactação teve um custo: o SIKE era de 100 a 1.000 vezes mais lento que os outros candidatos. Quando Castryck e Decru quebraram o SIKE em julho de 2022 usando um ataque clássico executado em minutos em um computador portátil, o SIKE foi imediatamente eliminado da competição da NIST.

A criptografia baseada em isogenias ocupa uma posição única entre as abordagens pós-quânticas. Tamanhos de chave: muito menores que os de reticulados (ML-KEM: mais de 800 octetos) ou de assinaturas baseadas em funções de resumo (SLH-DSA: chave pública de 32–49 octetos, mas assinaturas de 7856–49856 octetos). Desempenho: muito mais lento que todas as alternativas (o SIKE era de 100 a 1.000 vezes mais lento que o ML-KEM). Hipótese de segurança: distinta de LWE (usado em ML-KEM/ML-DSA), SIS ou funções de resumo — fornece diversidade criptográfica. Base da segurança pós-quântica: o problema do caminho de isogenia não tem um algoritmo quântico conhecido de tempo polinomial, ao contrário de RSA/ECC, que o algoritmo de Shor quebra completamente. A quebra clássica do SIKE demonstra que a dificuldade das isogenias ainda está sendo compreendida, ao contrário do problema LWE, que é bem estudado.

Apesar da quebra do SIKE, a criptografia baseada em isogenias continua sendo uma área de pesquisa ativa. SQISign (Assinatura Curta de Quatérnios e Isogenia) é um esquema de assinatura baseado em isogenias com assinaturas de 177 octetos (contra 2420 octetos da ML-DSA para o Nível 2) — as menores assinaturas de PQC conhecidas. O SQISign usa o problema difícil de calcular uma isogenia de grau prescrito entre duas curvas supersingulares dadas, formalizado como o problema do anel de endomorfismos. FESTA (Criptografia Rápida a partir de Ataques de Torção Supersingular) é um novo projeto de KEM que evita os dados auxiliares extras de pontos de torção que tornaram o SIDH vulnerável. CTIDH (CSIDH de tempo constante) melhora o desempenho do CSIDH. Esses esquemas mantêm a pesquisa sobre isogenias relevante mesmo após a eliminação do SIKE.

O que é uma isogenia entre curvas elípticas?

Uma isogenia é uma aplicação racional phi: E -> E' que é um homomorfismo de grupos, com grau igual ao tamanho de seu núcleo. As fórmulas de Velu calculam a curva imagem e a aplicação a partir do subgrupo núcleo. Os grafos de isogenias organizam as curvas como vértices com arestas de grau l, formando grafos de Ramanujan regulares de grau l+1. As curvas supersingulares (usadas em SIDH/SIKE/CSIDH) têm grafos de isogenias com forte expansão. Os problemas SSIP e CSSI fundamentam a segurança das isogenias. O SIDH usa a estrutura dos pontos de torção com cadeias alternadas de isogenias de grau 2 e 3. O cálculo do anel de endomorfismos é equivalente ao SSIP. SQISign e FESTA representam direções ativas de pesquisa pós-SIKE que usam a dificuldade do anel de endomorfismos.