Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Enunciado do Problema
O artigo aborda a estimativa de recursos do algoritmo de Shor para o cálculo de logaritmos discretos de curvas elípticas (ECDL), uma ameaça primária à criptografia de chave pública atual. Embora trabalhos recentes de Babbush et al. (arXiv 2026) tenham demonstrado reduções significativas nas contagens de portas e qubits para a curva secp256k1, eles dependeram de uma prova de conhecimento zero para validar seus resultados sem revelar os circuitos quânticos lógicos subjacentes. Essa falta de transparência dificulta a reprodutibilidade e a verificação independente. O artigo visa fornecer uma arquitetura de circuito quântico lógico totalmente detalhada e reprodutível que alcance eficiência comparável à de Babbush et al., enquanto revela explicitamente os princípios de design e detalhes de implementação.

Metodologia
Os autores empregam uma abordagem de cima para baixo (top-down), partindo da estrutura de alto nível do algoritmo de Shor e refinando os componentes aritméticos. O núcleo da otimização reside na implementação da adição de pontos com janela (windowed point addition) em curvas elípticas sobre corpos primos.

1. Estrutura de Alto Nível: O algoritmo utiliza uma transformada de Fourier semiclássica com reciclagem de qubits para reduzir a multiplicação de pontos $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ a uma sequência de adições de pontos com janela. Os pontos são representados em coordenadas afins.
2. Multiplicação Modular In-Place: A operação mais dispendiosa na adição de pontos é a multiplicação modular in-place $|x, y\rangle \to |x, yx \pmod q|$. Os autores adaptam uma técnica de [14] que desacopla o Algoritmo de Euclides Estendido (EEA) em duas fases distintas:
   • Algoritmo de Euclides (Frente/Forward): Em vez de calcular diretamente os coeficientes de Bézout, esta fase processa as entradas $(q, x)$ e gera um vetor de bits de "lixo" (garbage) codificando a sequência de operações (trocas, subtrações, divisões por 2). Isso reduz a complexidade de espaço.
   • Reconstrução de Bézout (Trás/Backward): Esta fase recebe o vetor de bits de lixo e aplica as operações registradas a um par $(y, 0)$ para calcular $|y, yx^{-1} \pmod q\rangle$. Ao executar isso de forma reversa ou com entradas específicas, os autores alcançam a multiplicação e a inversão in-place simultaneamente.
3. Otimização Aritmética:
   • Trocas entre Espaço vs. Portas: Os autores alternam estrategicamente entre o somador CDKM (baixo espaço) e o somador Gidney (baixa contagem de portas, maior espaço), dependendo da disponibilidade de qubits ancila durante diferentes estágios do algoritmo.
   • Aritmética Aproximada: Para reduzir as contagens de portas, os autores introduzem circuitos de aritmética aproximada. As comparações são realizadas utilizando apenas os bits mais significativos (MSBs) em vez de comparações de largura total. Isso introduz uma probabilidade de falha, que é gerenciada pela otimização de constantes para garantir o sucesso em entradas aleatórias com alta probabilidade (especificamente, probabilidade de falha $\le 2^{-13.3}$).
   • Otimização Específica da Instância: Para a curva secp256k1, que utiliza um primo pseudo-Mersenne ($q = 2^{256} - 4294968273$), os circuitos de redução modular são ainda mais simplificados. Os autores exploram a pequena diferença $f$ na forma $2^u - f$ para substituir subtrações modulares caras por manipulações de bits simples e adições de $f$.

Principais Contribuições

• Arquitetura de Circuito Reprodutível: O artigo detalha o primeiro circuito quântico lógico totalmente especificado para ECDL na secp256k1 que iguala as reivindicações de eficiência do trabalho opaco de Babbush et al. O código é implementado e está disponível via biblioteca Qarton.
• Contagens de Recursos Otimizadas: Os autores apresentam duas variantes do circuito:
  • Otimizada para Espaço: Utiliza aproximadamente $4.36n + O(\sqrt{n})$ qubits.
  • Otimizada para Portas: Utiliza aproximadamente $4.36n + O(\sqrt{n})$ qubits, mas reduz a contagem de portas Toffoli.
• Variante Genérica: Uma versão do circuito é fornecida que é válida para qualquer corpo primo, não apenas para secp256k1, embora incorra em um custo de portas ligeiramente superior devido à ausência de otimizações de pseudo-Mersenne.
• Análise de Custo Detalhada: O artigo fornece uma decomposição granular dos custos de portas Toffoli, distinguindo entre a construção do GCD, a reconstrução de Bézout e os componentes de aritmética modular.

Resultos
Os autores relatam as seguintes estimativas de recursos para a curva secp256k1 (onde $n=256$):

• Contagem de Qubits:
  • Variante otimizada para espaço: 1.192 qubits (comparado a 1.175 em Babbush et al.).
  • Variante otimizada para portas: 1.446 qubits (comparado a 1.425 em Babbush et al.).
  • Isso representa um aumento de aproximadamente 1,5% na contagem de qubits.
• Contagem de Portas (Toffolis):
  • Variante otimizada para espaço: $2^{21.19}$ (aprox. $2,3 \times 10^6$).
  • Variante otimizada para portas: $2^{20.83}$ (aprox. $1,8 \times 10^6$).
  • Isso representa uma redução de 6,5% a 10% na contagem de portas Toffoli em comparação com Babbush et al.
• Custo do Algoritmo Completo: Para o algoritmo de Shor completo na secp256k1, a variante otimizada para portas requer aproximadamente $2^{25.78}$ portas Toffoli e 1.462 qubits. Este é um avanço significativo em relação ao trabalho anterior de Litinski (arXiv 2023), que exigia cerca de $2^{27.57}$ portas Toffoli e o dobro do número de qubits.

Significância
O artigo reivindica significância principalmente no domínio da reprodutibilidade e transparência. Ao fornecer a arquitetura explícita do circuito lógico, os autores permitem que a comunidade criptográfica verifique as estimativas de recursos para quebrar a criptografia de curva elíptica, que anteriormente estavam ocultas atrás de uma prova de conhecimento zero. O trabalho demonstra que uma eficiência semelhante ou ligeiramente melhorada pode ser alcançada através de escolhas de design explícitas, especificamente a separação do EEA em uma fase de registro e uma fase de reconstrução, combinada com aritmética aproximada. Os autores observam que seus circuitos não são exatos e dependem de uma alta probabilidade de sucesso em entradas aleatórias, uma propriedade compartilhada com o trabalho que replicam. Os resultados confirmam que o custo de quebrar a secp256k1 é menor do que estimado anteriormente por alguns modelos de circuitos lógicos, reforçando a urgência da migração pós-quântica.