O Futuro da Criptografia Baseada em Isogenias

A quebra do SIKE por Castryck-Decru, em julho de 2022, mudou drasticamente a área das isogenias. Antes da quebra, a criptografia baseada em isogenias era uma direção pós-quântica promissora, com tamanhos de chave pequenos, esforços ativos de padronização e uma comunidade em crescimento. Após a queda do SIKE, a área foi obrigada a reexaminar seus fundamentos. A questão principal é: quais aspectos da criptografia baseada em isogenias continuam difíceis após as novas técnicas de isogenias de Richelot? A resposta parece ser: a dificuldade baseada em anéis de endomorfismos (usada no SQISign) e as ações comutativas de grupos de classes (CSIDH) continuam intactas. O componente quebrado é o vazamento de pontos de torção auxiliares específico do SIDH, e não as isogenias em geral.

O SQISign (assinatura curta de quaternião e isogenia, De Feo et al., 2020) é o esquema de assinatura pós-quântica conhecido mais compacto. Chave pública: 64 bytes (um j-invariante supersingular). Assinatura: 177 bytes no Nível 1. Para comparação, o ML-DSA (Dilithium) tem chaves públicas de 1312 bytes e assinaturas de 2420 bytes no Nível 2. A segurança do SQISign baseia-se na correspondência de Deuring: o problema de calcular uma isogenia de grau prescrito entre duas curvas supersingulares dadas equivale a encontrar um ideal na álgebra de quatérnios do anel de endomorfismos. O SQISign usa um esquema de identificação Fiat-Shamir sobre esse problema difícil, produzindo uma assinatura como uma representação comprimida da isogenia de resposta.

O tamanho compacto do SQISign tem um custo severo de desempenho. A assinatura exige o cálculo de uma isogenia de grau elevado (aproximadamente p^{1/4}) usando a conversão de ideal em isogenia na álgebra de quatérnios — uma operação computacionalmente intensiva que leva aproximadamente 60–600 segundos em uma CPU de computador de mesa, dependendo do conjunto de parâmetros. A verificação é mais rápida (cerca de 200 ms), mas ainda muito mais lenta do que a verificação do ML-DSA (microssegundos). O SQISign 2.0 (2023) melhorou o desempenho em 100 vezes por meio de aprimoramentos algorítmicos, reduzindo o tempo de assinatura para 1–10 segundos. O SQISign HD (grau elevado) e outras variantes continuam o processo de otimização. A aplicação-alvo são casos de uso nos quais a largura de banda é extremamente limitada (certificados para a Internet das Coisas, dados de cadeias de blocos, comunicações espaciais) e a velocidade computacional é secundária.

O FESTA (cifragem rápida a partir de ataques de torção supersingular, 2023) é um KEM projetado especificamente para evitar o vazamento de pontos de torção no estilo do SIDH. A principal ideia de projeto é: em vez de publicar phi_A(P_B) e phi_A(Q_B), como no SIDH, o FESTA usa uma estrutura de isogenia diferente, na qual a chave pública do cifrador é apenas a curva imagem (sem imagens de torção). O FESTA usa isogenias 2^n de uma maneira modificada que permite a decifragem sem as imagens da base de torção da outra parte. As análises iniciais sugerem que o FESTA resiste ao ataque de Castryck-Decru devido à sua estrutura diferente de informações auxiliares. O FESTA é uma direção promissora, mas exige uma análise criptoanalítica mais aprofundada — a comunidade de isogenias está cautelosa após a quebra inesperada do SIKE.

O SCALLOP (ações comutativas escaláveis com primos orientados grandes, 2023) aborda a fragilidade da segurança quântica do CSIDH. O primo pequeno p = 512 bits do CSIDH oferece apenas aproximadamente 65 bits de segurança quântica (contra o algoritmo subexponencial de Kuperberg). O SCALLOP usa uma estrutura algébrica diferente: curvas com multiplicação complexa por ordens quadráticas imaginárias grandes, nas quais o grupo de classes é projetado especificamente para resistir a ataques quânticos no estilo de Kuperberg. O SCALLOP obtém um grupo de classes efetivo maior, com parâmetros que oferecem segurança quântica de 128 bits usando tamanhos de parâmetros menores do que os do CSIDH-5000. O compromisso é que a configuração algébrica do SCALLOP é mais complexa e recebeu menos análises independentes do que o CSIDH.

Considerando o tamanho compacto exclusivo dos esquemas baseados em isogenias (assinaturas de 177 bytes do SQISign, chaves de 64 bytes do CSIDH) e seus pressupostos de dificuldade distintos dos esquemas baseados em reticulados, as construções híbridas combinam componentes de isogenias e de reticulados para oferecer defesa em profundidade. Um KEM híbrido: encapsular com ML-KEM-512 AND com CSIDH-512 e aplicar uma função de resumo aos dois segredos juntos. A chave combinada exige a quebra simultânea do ML-KEM (dificuldade do LWE) e do CSIDH (ação do grupo de classes). Se qualquer um deles permanecer sem ser quebrado, o esquema híbrido será seguro. Essa abordagem de agilidade criptográfica é endossada pelo NIST e pela NSA para organizações que desejam uma garantia adicional além de qualquer primitiva pós-quântica individual, especialmente quando os prazos para a chegada dos computadores quânticos são incertos.

As provas de conhecimento zero baseadas em isogenias são uma direção de pesquisa emergente. O problema do caminho de isogenia (encontrar phi: E -> E' dadas as duas curvas) pode servir como um problema difícil para esquemas de prova de conhecimento. Os protocolos Sigma para “Conheço uma isogenia de E para E'” permitem a autenticação sem revelar a isogenia. O Vero (2022) demonstra um sistema prático de provas de conhecimento zero baseado em isogenias. Essas provas de conhecimento zero são naturalmente compactas (a afirmação consiste apenas em dois j-invariantes), mas atualmente são lentas demais para implantação prática. À medida que o cálculo de isogenias melhorar, as provas de conhecimento zero baseadas em isogenias poderão oferecer alternativas às provas baseadas em reticulados ou em funções de resumo, quando a diversidade de pressupostos for valorizada.

As técnicas de isogenia não são relevantes apenas para a criptografia pós-quântica — elas também têm aplicações na criptografia clássica de curvas elípticas. O algoritmo de Schoof-Elkies-Atkin (SEA) para contar pontos em curvas elípticas usa isogenias para calcular o traço de Frobenius, permitindo a geração eficiente de parâmetros seguros para curvas elípticas. As isogenias aparecem em aprimoramentos do método rho de Pollard para o cálculo de ECDLP. O método de CM (multiplicação complexa) para construir curvas com ordem prescrita usa polinômios de classes que são fundamentalmente objetos de isogenia. As ferramentas de criptoanálise baseadas em isogenias (para encontrar caminhos de isogenias de grau suave) são usadas para avaliar parâmetros propostos de curvas elípticas em busca de portas dos fundos ocultas — uma questão diretamente relacionada à preocupação com o Dual EC DRBG.

Em 2024, nenhum esquema baseado em isogenias foi padronizado pelo NIST ou por outros organismos importantes. O processo de PQC do NIST padronizou ML-KEM, ML-DSA, SLH-DSA e FN-DSA — todos baseados em reticulados ou em funções de resumo. O NIST está conduzindo uma segunda rodada de avaliação de assinaturas de PQC; o SQISign foi submetido, mas enfrenta preocupações de desempenho. A comunidade de isogenias trabalha para alcançar um SQISign 3.0 mais maduro, com tempos práticos de assinatura (meta de menos de um segundo). ISO e ETSI não padronizaram nenhum esquema baseado em isogenias. O caminho de padronização mais provável no curto prazo é o SQISign para aplicações de nicho que exigem tamanhos mínimos de assinatura, possivelmente como um padrão informativo, e não como uma primitiva obrigatória. A implantação ampla exige melhorias de desempenho de uma ordem de grandeza.

Direções ativas de pesquisa em criptografia baseada em isogenias em 2024: (1) variantes do SQISign (SQISign 2.0, HD, Fast SQISign) que melhoram o desempenho da assinatura, aproximando a operação de menos de um segundo. (2) Análise da segurança quântica do CSIDH e de suas variantes — refinamento das estimativas dos ataques de Kuperberg e exploração de estruturas algébricas que resistam a eles. (3) Novos pressupostos de dificuldade — cálculos de anéis de endomorfismos supersingulares e problemas de módulos sobre anéis quadráticos imaginários. (4) Funções pseudoaleatórias cegas baseadas em isogenias e aplicações em protocolos de preservação da privacidade. (5) Implementações em componentes físicos da aritmética de isogenias — aproveitamento do paralelismo de FPGA para a ação do grupo de classes do CSIDH. (6) Integração das ações de grupo baseadas em isogenias com estruturas gerais de criptografia de ações de grupo para criar novos esquemas de criptografia funcional e baseados em atributos.

A quebra do SIKE pode sugerir abandonar completamente a criptografia baseada em isogenias. A comunidade criptográfica adota a visão oposta: a quebra foi valiosa precisamente porque identificou quais estruturas não são seguras (o vazamento de pontos de torção do SIDH) e quais continuam difíceis (anéis de endomorfismos, ações de grupos de classes). Estudar isogenias continua importante por: (1) diversidade pós-quântica — ter hipóteses de segurança além de reticulados reduz o risco sistêmico caso o LWE seja quebrado; (2) SQISign fornece assinaturas excepcionalmente compactas, sem concorrentes atualmente; (3) as técnicas de isogenias contribuem para a criptoanálise de curvas elípticas e a validação de parâmetros; (4) a matemática é bela e produtiva — as ferramentas desenvolvidas para a quebra do SIKE melhoraram diretamente a compreensão dos anéis de endomorfismos de curvas elípticas usados em outros contextos.

Qual é a hipótese de dificuldade subjacente às assinaturas SQISign?

Após a quebra do SIKE em 2022, a criptografia de isogenias continua com diferentes hipóteses de dificuldade. SQISign fornece assinaturas pós-quânticas de 177 bytes (as menores conhecidas), baseadas na dificuldade dos anéis de endomorfismos; o desempenho está melhorando (a meta é ficar abaixo de um segundo). FESTA é projetado para levar em conta o vazamento de pontos de torção do SIDH em mecanismos de encapsulamento de chaves. SCALLOP tem como meta oferecer segurança quântica de 128 bits por meio de curvas orientadas. Esquemas híbridos de isogenias e reticulados oferecem diversidade de hipóteses. Atualmente, nenhum esquema de isogenias é padronizado. A padronização do SQISign é o caminho mais provável no curto prazo. A quebra do SIKE aprofundou a compreensão do que precisa ser ocultado nos protocolos de isogenias e produziu novas ferramentas matemáticas usadas em toda a criptografia de curvas elípticas.