⚛️ quantum physics

CRT-Decomposed $Σ$ -Protocols for CSIDH

Este artigo apresenta um protocolo $\Sigma$ decomposto por CRT para CSIDH que alcança completude perfeita, conhecimento zero e extração direta eficiente no QROM sem suposições heurísticas, enquanto verifica rigorosamente sua correção algébrica e demonstra que sua segurança atualmente depende de parâmetros futuros com fatores primos grandes devido a uma redução significativa no custo de ataque clássico quando curvas de salto CRT são publicadas.

Autores originais: I. Dey, I. Cherkaoui

Publicado 2026-09-23

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: I. Dey, I. Cherkaoui

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No mundo digital, a privacidade muitas vezes depende de um equilíbrio delicado: um usuário deseja provar que tem o direito de gastar dinheiro ou acessar um serviço sem revelar sua identidade ou os detalhes específicos da transação. Este é o domínio das assinaturas cegas, uma ferramenta criptográfica que permite a um banco certificar uma moeda sem jamais ver onde ela será gasta. Por décadas, a segurança desses sistemas repousou em enigmas matemáticos envolvendo números grandes, mas a ascensão de computadores quânticos poderosos ameaça resolver esses enigmas, tornando obsoletas as atuais proteções de privacidade. Para combater isso, cientistas estão recorrendo a um tipo diferente de matemática baseada na geometria de curvas elípticas, especificamente um método chamado criptografia baseada em isogenias. Essa abordagem utiliza um tipo único de movimento entre curvas que é fácil de realizar em uma direção, mas incrivelmente difícil de reverter, criando uma base para uma segurança que máquinas quânticas não conseguem quebrar facilmente. No entanto, construir sistemas práticos sobre essa base tem sido difícil porque os métodos padrão para provar o conhecimento de uma chave secreta frequentemente dependem de um processo que falha ao enfrentar adversários quânticos.

Uma equipe de pesquisadores da South East Technological University, na Irlanda, desenvolveu uma nova maneira de construir essas provas que evita as fraquezas fatais dos métodos anteriores. O trabalho deles foca em um sistema específico conhecido como CSIDH, que utiliza uma estrutura matemática chamada grupo de classes para se mover entre curvas elípticas. Os pesquisadores descobriram que, quando a estrutura interna deste grupo é totalmente conhecida, como é o caso de uma versão específica chamada CSIDH-512, ela pode ser decomposta em partes menores e independentes usando um princípio matemático clássico conhecido como Teorema Chinês dos Restos. Em vez de tratar a chave secreta como um bloco único e monolítico, eles projetaram um protocolo que prova o conhecimento de cada pequena parte separadamente. Essa mudança estrutural permite que o sistema extraia a chave secreta diretamente da prova usando aritmética simples, em vez de depender de um jogo de adivinhação complexo e repetitivo que computadores quânticos podem interromper.

O cerne de sua conquista é um novo tipo de prova interativa que é perfeitamente completa e perfeitamente segura contra interceptações. Neste sistema, um provador e um verificador trocam mensagens para confirmar que o provador conhece uma chave secreta sem revelar a chave em si. Os pesquisadores provaram que, se um provador conseguir responder a dois desafios diferentes para a mesma etapa, o segredo pode ser recuperado instantaneamente subtraindo as respostas e realizando uma única divisão. Esse processo, que eles chamam de extração algébrica, acontece em linha reta, sem a necessidade de retroceder ou reiniciar a interação. Esta é uma distinção crítica, pois as provas de segurança anteriores para sistemas semelhantes dependiam de retroceder o atacante a um estado anterior para forçar um erro, uma técnica que é impossível de justificar contra um computador quântico que não pode ser pausado ou copiado. Ao remover este passo, o novo protocolo oferece um caminho para a segurança que se mantém mesmo em um futuro onde computadores quânticos sejam comuns.

Para garantir que seu design não fosse apenas uma ideia teórica, a equipe implementou todo o sistema em um computador usando os parâmetros exatos do grupo CSIDH-512. Eles verificaram a lógica matemática do protocolo ao longo de dez mil instâncias aleatórias, confirmando que as etapas algébricas funcionaram exatamente como previsto todas as vezes. Eles também realizaram simulações para medir como o sistema se comportaria sob ataque. Esses testes confirmaram que a segurança do sistema segue as leis matemáticas esperadas, com a dificuldade de quebrá-lo crescendo previsivelmente à medida que o número de rodadas aumenta. No entanto, os pesquisadores também foram cuidadosos em identificar os limites de sua abordagem. Eles demonstraram que, embora dividir o problema em partes menores torne a extração do segredo possível, isso também expõe o sistema a um tipo específico de ataque que reduz a dificuldade de quebrar a chave. Para os parâmetros atuais do CSIDH-512, essa redução diminui a segurança de um nível que exigiria aproximadamente 2^128.6 avaliações de ação de grupo para cerca de 2^67.3 avaliações, uma queda significativa que torna os parâmetros atuais insuficientes para a segurança clássica de 128 bits.

Consequentemente, os pesquisadores concluem que, embora sua construção seja matematicamente correta e estruturalmente completa, ela ainda não é segura para implantação imediata nos parâmetros atuais do CSIDH-512. O sistema funciona perfeitamente, mas a própria característica que o torna eficiente — a exposição de etapas intermediárias — também o torna vulnerável a um método de ataque conhecido. A solução, argumentam eles, reside em conjuntos de parâmetros futuros onde os componentes matemáticos sejam muito maiores. Se o grupo for construído a partir de fatores primos que são individualmente muito grandes, a perda de segurança pela exposição das etapas intermediárias torna-se negligenciável, e o sistema permaneceria seguro. O artigo também comparou seu método com esquemas existentes, observando que, embora suas assinaturas sejam atualmente maiores, a compensação é um modelo de segurança que não se degrada ao enfrentar ameaças quânticas. O trabalho serve como uma demonstração rigorosa de que a estrutura algébrica pode substituir provas de segurança complexas e propensas a erros, desde que os números subjacentes sejam escolhidos com cuidado suficiente para resistir às novas vulnerabilidades que a estrutura introduz.

Resumo Técnico: Protocolos $\Sigma$ -Decompostos por CRT para Ações de Grupo de CSIDH

Definição do Problema
O artigo aborda uma fraqueza crítica nas provas de segurança de protocolos de assinaturas cegas e identificação baseados em isogenias, especificamente aqueles construídos sobre a ação de grupo CSIDH (Commutative Supersingular Isogeny Diffie-Hellman). Os esquemas de estado da arte atuais (ex: CSI-Otter, Tanuki) dependem de protocolos de identificação interativos cuja redução de segurança depende do lema do forking (forking lemma). Este lema exige o "rewinding" (rebobinamento) de um adversário quântico para extrair uma chave secreta, um processo que incorre em uma perda quadrática de segurança e é teoricamente inválido contra adversários quânticos cujos estados internos não podem ser clonados. Consequentemente, essas provas forçam o uso de parâmetros maiores e mais lentos para compensar essa perda. O artigo busca eliminar esse passo de rewinding aproveitando a estrutura algébrica do grupo de classes do CSIDH para permitir a extração em linha reta (straight-line extraction).

Metodologia
Os autores constroem uma prova de conhecimento de zero-conhecimento (protocolo $\Sigma$ ) que explora a estrutura do Teorema Chinês dos Restos (CRT - Chinese Remainder Theorem) do grupo de classes de CSIDH. Esta abordagem é aplicável apenas quando a estrutura do grupo é exatamente conhecida, uma condição atualmente atendida apenas pelo CSIDH-512.

Decomposição por CRT: O grupo de classes $C\ell(\mathcal{O})$ de ordem $N$ é decomposto em componentes cíclicos independentes correspondentes aos fatores de potência de primos de $N$ . A chave secreta $s$ é dividida em componentes $s_i$ módulo cada fator primo $q_i$ .
Curvas de Salto (Hop Curves): O protocolo publica uma cadeia de "curvas de salto" ( $F_0, \dots, F_k$ ) representando os estados intermediários da ação de grupo. Cada salto $i$ corresponde a um problema de vetorização dentro de um subgrupo específico $\langle h_i \rangle$ de ordem $q_i$ .
Estrutura do Protocolo: O protocolo consiste em $k$ saltos, cada um executado em $t$ rodadas paralelas. Em cada rodada, o provador compromete-se com um deslocamento aleatório, o verificador emite um desafio binário ( $c \in \{0,1\}$ ) e o provador responde com um valor $z$ .
Extração Algébrica: Ao contrário das provas padrão que exigem rewinding para encontrar dois transcritos aceitáveis com desafios diferentes, este protocolo permite que o segredo seja recuperado via uma fórmula algébrica de forma fechada. Dados dois transcritos aceitáveis para o mesmo compromisso, o componente do segredo é simplesmente a diferença das respostas ( $z_0 - z_1$ ), seguida de inversão modular e recombinação por CRT.
Compilação QROM: Como cada rodada admite exatamente duas respostas, o protocolo é compatível com a transformação de Unruh. Isso permite a conversão do protocolo interativo em uma prova de conhecimento não interativa no Modelo de Oráculo Aleatório Quântico (QROM) com extração em linha reta, evitando completamente o lema do forking.

Principais Contribuições
O artigo apresenta cinco contribuições primárias:

Definição Formal: Ele formaliza a extraibilidade fraca (weak extractability) para ações de grupo criptográficas, definindo uma noção de segurança onde um extrator pode recuperar o segredo usando apenas operações de anel (sem redução de rede ou heurísticas) a partir de transcritos aceitáveis.
Construção do Protocolo ( $\Pi_{CRT}$ ): Constrói um protocolo que prova quatro propriedades:
- Completude Perfeita: Provadores honestos sempre têm sucesso.
- HVZK Especial Perfeito: Os transcritos não revelam informações sobre o segredo, mesmo para observadores ilimitados.
- 2-Soundness Especial: O segredo é algebricamente recuperável de dois transcritos via subtração simples e inversão modular.
- Erro de Conhecimento: A probabilidade de um provador ter sucesso sem a chave é $2^{-t}$ .
Verificação de Máquina: Os autores implementaram a camada algébrica sobre o módulo exato de 258 bits do CSIDH-512. Eles verificaram 10.000 instâncias aleatórias, confirmando que a extração algébrica funciona perfeitamente e que a lógica do protocolo se mantém sem computar isogenias reais.
Delimitação de Resultados (Resultados Negativos):
- Limite do Espaço de Desafio: A decomposição por CRT não amplia o espaço de desafio por rodada; desafios binários permanecem necessários, a menos que múltiplas curvas sejam publicadas, o que aumenta o tamanho da chave.
- Custo de Segurança: Publicar as curvas de salto intermediárias reduz a segurança clássica da recuperação de chave de $\approx 2^{128.6}$ para $\approx 2^{67.3}$ avaliações de ação de grupo. Isso ocorre porque o problema se decompõe em instâncias de vetorização independentes em subgrupos, solúveis via ataques de meet-in-the-middle no maior componente.
Segurança QROM: O artigo prova que o protocolo, quando compilado via transformação de Unruh, produz uma prova não interativa com extração online no QROM, removendo a perda multiplicativa do lema do forking.

Resultados e Análise Quantitativa

Instanciação: O esquema é instanciado no CSIDH-512. O grupo de classes possui 5 fatores primos (comprimentos de bits: 2, 6, 21, 96, 135).
Limites de Segurança:
- Clássica: A segurança é limitada pelo maior fator primo ( $q_{max} \approx 2^{135}$ ). O custo do ataque meet-in-the-middle é $O(\sqrt{q_{max}}) \approx 2^{67.3}$ . O artigo observa que o CSIDH-512 não atinge 128 bits de segurança clássica sob esta construção devido às curvas de salto publicadas.
- Quântica: A segurança é limitada por peneiras do tipo Kuperberg, de forma semelhante a outros esquemas CSIDH.
Desempenho:
- Tamanho da Assinatura: Para $t=128$ rodadas e $k=5$ componentes, o tamanho da assinatura é de aproximadamente 24,1 KiB (comparado a 263 B para CSI-FiSh e 8 KiB para CSI-Otter).
- Computação: A extração algébrica e a simulação são de sub-microssegundos. O custo dominante permanece a avaliação da isogenia (projetada em 40 ms por ação), tornando o tempo total de assinatura de aproximadamente 25,6 segundos para o protocolo completo.
Simulação: Simulações de Monte Carlo confirmaram que o erro de soundness condiz com o limite teórico de $2^{-t}$ dentro de intervalos de confiança de 95%.

Significância e Alegações
O artigo afirma que a construção é estruturalmente completa e correta para grupos de classes de estrutura conhecida como CSIDH-512. Sua principal significância reside em fornecer uma redução de segurança segura para o computador quântico (quantum-safe) para provas de conhecimento baseadas em isogenias ao eliminar o passo de rewinding, que é uma vulnerabilidade conhecida em provas de segurança pós-quânticas.

No entanto, os autores são explícitos sobre as compensações (trade-offs):

Modéstia sobre a Segurança: O esquema não é quantitativamente seguro no nível de 128 bits para o CSIDH-512 devido à degradação de segurança causada pela publicação das curvas de salto. Os autores afirmam que a construção é "quantitativamente segura apenas em futuros conjuntos de parâmetros cujos números de classe possuam fatores primos grandes" (ex: onde cada fator é $\ge 256$ bits).
Não é uma Solução Mágica: A decomposição por CRT não reduz o número de rodadas necessárias para o soundness; ela apenas altera o mecanismo de extração.
Trabalho Futuro: O artigo deixa a construção de uma assinatura cega baseada nesta prova de conhecimento e a redução estrita de sua não-falsificabilidade ao problema do anel de endomorfismos como trabalhos futuros.

Em resumo, o artigo apresenta um protocolo matematicamente rigoroso e verificado por máquina que resolve o "problema do rewinding" para provas de conhecimento baseadas em CSIDH, oferecendo um caminho para assinaturas cegas seguras em QROM, mas ao custo de tamanhos de assinatura maiores e redução da segurança clássica para os conjuntos de parâmetros atuais.

Mais como este