Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field

Resumo Técnico: Algoritmo de Cálculo de Índice Duplo para Problemas de Logaritmo Discreto

Declaração do Problema
O artigo aborda o Problema do Logaritmo Discreto (PLD) em corpos finitos primos, um problema computacional fundamental que sustenta a segurança de inúmeros esquemas criptográficos, incluindo criptografia de chave pública e assinaturas digitais. Embora o algoritmo de Cálculo de Índice e suas variantes (como a Triagem de Corpo Numérico e a Triagem de Corpo de Funções) representem o estado da arte para resolver o PLD nesses corpos, eles enfrentam limitações específicas. Primariamente, esses algoritmos exigem o cálculo de logaritmos discretos para todos os primos em uma base de fatoração (tamanho $k$) mais o inteiro alvo, totalizando $k+1$ logaritmos, antes que o alvo possa ser resolvido. Além disso, os algoritmos padrão de Cálculo de Índice frequentemente falham se a base do PLD não for um gerador de multiplicação do corpo, pois os logaritmos discretos de certos primos na base de fatoração podem não existir.

Metodologia: O Algoritmo de Cálculo de Índice Duplo
Os autores propõem o "Algoritmo de Cálculo de Índice Duplo", que altera fundamentalmente a abordagem para resolver o PLD, reduzindo o número de logaritmos discretos necessários.

1. Sistemas de Equações Duais: Em vez de fixar uma única equação alvo, o algoritmo constrói dois sistemas separados de equações lineares:
   • Um sistema calcula os logaritmos discretos dos primos na base de fatoração em relação ao gerador $g$ (encontrando $\log_g p_i$).
   • Um segundo sistema calcula os logaritmos discretos dos mesmos primos em relação à base alvo $b$ (encontrando $\log_b p_i$).
2. Estratégia de Interseção: A inovação central reside em identificar um primo $p_i$ na base de fatoração para o qual ambos $\log_g p_i$ e $\log_b p_i$ foram calculados com sucesso.
3. Solução do Alvo: Uma vez encontrado tal primo, o algoritmo resolve o logaritmo discreto alvo $x$ (onde $g^x \equiv b \pmod p$) usando a relação:
   $$x \equiv \alpha \beta^{-1} \pmod{p-1}$$
   onde $g^\alpha \equiv p_i \pmod p$ e $b^\beta \equiv p_i \pmod p$.
4. Eficiência Probabilística: O algoritmo depende da natureza probabilística de encontrar inteiros lisos. Enquanto o algoritmo padrão de Cálculo de Índice deve resolver determinadamente $k+1$ logaritmos, o Algoritmo de Cálculo de Índice Duplo pode ter sucesso assim que a interseção dos dois conjuntos de logaritmos calculados for não vazia. Os autores argumentam que o número de "casos bons" (cenários onde o alvo é solucionável com menos de $k+1$ logaritmos) é massivo, levando a uma alta probabilidade de término antecipado.
5. Paralelização: O cálculo dos logaritmos na base $g$ e na base $b$ são processos independentes, permitindo execução paralela, o que reduz ainda mais o tempo total de execução para o máximo dos dois processos paralelos, em vez de sua soma.

Principais Contribuições

• Avanço Teórico: O artigo afirma uma redução teórica no número de logaritmos discretos necessários. Enquanto os métodos tradicionais exigem $k+1$ logaritmos, o algoritmo proposto pode resolver o problema com menos de $k+1$ logaritmos, aproveitando a interseção de dois conjuntos parciais de logaritmos.
• Generalidade Aprimorada: O algoritmo é projetado para funcionar mesmo quando a base $g$ não é um gerador de multiplicação do corpo. Nesses casos, onde o Cálculo de Índice padrão pode falhar porque $\log_g p_i$ não existe para alguns primos, o Cálculo de Índice Duplo ainda pode ter sucesso, desde que exista pelo menos um primo para o qual tanto $\log_g p_i$ quanto $\log_b p_i$ existam.
• Compatibilidade: O método é compatível com técnicas de otimização existentes (como métodos de triagem) usadas para acelerar a descoberta de inteiros lisos. Pode utilizar esses truques para encontrar inteiros lisos mais rapidamente e, em seguida, aplicar sua própria lógica para reduzir o número de inteiros lisos necessários.

Resultados Experimentais
Os autores conduziram extensos experimentos empíricos comparando seu algoritmo ao algoritmo padrão de Cálculo de Índice e a outros métodos clássicos (Passo a Passo Gigante, Rho, Pohlig-Hellman).

• Aceleração: Para corpos finitos primos com comprimento de bits de 70, o Algoritmo de Cálculo de Índice Duplo demonstrou uma aceleração de aproximadamente 34 vezes em comparação com o algoritmo de Cálculo de Índice (2211 segundos vs. 75426 segundos).
• Escalabilidade: A lacuna de desempenho aumenta à medida que o comprimento de bits aumenta. Em 50 bits, o algoritmo proposto foi cerca de 10 vezes mais rápido; em 70 bits, foi mais de 30 vezes mais rápido.
• Limite de Lisidade: Os experimentos indicaram que o limite de lisidade ótimo para o algoritmo proposto difere ligeiramente do Cálculo de Índice padrão (frequentemente em torno de $0,65B_i$ vs. $0,5B_i$), mas o algoritmo proposto manteve consistentemente um tempo médio de execução menor em vários comprimentos de bits (30 a 75 bits).

Significado e Afirmações
O artigo posiciona o Algoritmo de Cálculo de Índice Duplo como uma melhoria significativa sobre o estado da arte atual para resolver o PLD em corpos finitos primos. Os autores afirmam que, ao reduzir o número de logaritmos discretos que devem ser calculados, o algoritmo alcança um aumento substancial na velocidade de computação. Eles afirmam que essa melhoria não é meramente uma variação dos métodos de triagem existentes, mas uma mudança estrutural no processo de resolução. Os autores sugerem que esses resultados podem influenciar como os pesquisadores selecionam parâmetros de segurança para esquemas criptográficos que dependem da dificuldade do PLD, pois o nível de segurança efetivo de um determinado tamanho de chave pode ser inferior ao estimado anteriormente pelos modelos de complexidade padrão do Cálculo de Índice.