Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Resumo Técnico: Ataque Quântico Probabilístico Polinomial a Module-LWE sobre Ciclotômicos de Potência de 2

Enunciado do Problema
O artigo aborda a segurança de esquemas criptográficos baseados em Module Learning With Errors (Module-LWE), focando especificamente no ML-KEM padronizado pelo NIST (antigo CRYSTALS-Kyber) e em esquemas relacionados baseados em reticulados (Falcon, Hawk, NTRU) construídos sobre anéis ciclotômicos de potência de 2 ($R = \mathbb{Z}[\zeta_{2^k}]$). O problema central é a recuperação de chaves secretas via o Problema do Vetor Mais Curto (SVP) em reticulados de módulos. Enquanto ataques clássicos dependem de algoritmos de redução de reticulados (por exemplo, BKZ) com complexidade exponencial, o artigo investiga se um adversário quântico pode explorar a estrutura algébrica dos anéis ciclotômicos para resolver o Problema do Ideal Principal (PIP) e o Problema do Gerador Curto (SGP) de forma eficiente.

Os autores identificam duas questões críticas não resolvidas em trabalhos anteriores (especificamente o ataque CDPR):

1. O fator de aproximação alcançado pelo ataque CDPR é suficientemente pequeno para quebrar chaves secretas completas do ML-KEM (ou seja, é $\gamma < q/2$)?
2. A sub-rotina quântica de PIP subjacente alcança complexidade verdadeiramente polinomial sem sobrecargas exponenciais ocultas ou dependência da Hipótese de Riemann Generalizada (GRH)?

Metodologia
O artigo apresenta um pipeline de ataque unificado de quatro fases (Algoritmo 1) que integra resultados das Partes I–III da série com um novo algoritmo quântico de tempo polinomial para PIP (Parte IV).

1. Redução de Módulo para Ideal: O ataque começa reduzindo a instância de Module-LWE para um Problema do Ideal Principal. Usando uma decomposição de Gram-Schmidt, a base do módulo é transformada em um produto de ideais principais. Os autores provam que a redução introduz apenas um fator constante $\alpha_d = O(1)$, independente do posto do módulo $d$.
2. PIP de Torre Quântica: Em vez de resolver o PIP no corpo completo $\mathbb{Q}(\zeta_{2^k})$ diretamente, os autores propõem uma estratégia de "decomposição em torre". Eles decompõem o corpo em uma cadeia de extensões quadráticas: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$.
   • Em cada nível $L$, o algoritmo resolve o PIP para a extensão relativa usando o Problema do Subgrupo Oculto Abeliano (HSP).
   • Crucialmente, o número de novos geradores de unidades em cada nível cresce linearmente ($\Delta r_L = 2^{L-3}$), mantendo o tamanho da instância do HSP polinomial.
   • Esta abordagem evita a explosão de coeficientes inerente às representações padrão de base de potência e elimina a necessidade da GRH, pois o número de classes do subcorpo real máximo é provado ser 1 para $k \le 12$.
3. CVP de Log-Unidades: Uma vez encontrado um gerador $g$ do ideal (que pode ser exponencialmente longo), o algoritmo calcula sua imersão logarítmica. Em seguida, resolve o Problema do Vetor Mais Próximo (CVP) no reticulado de log-unidades para encontrar a discrepância de unidade $\epsilon$ tal que $g = g_0 \epsilon$, onde $g_0$ é o gerador curto.
   • Os autores utilizam o algoritmo do plano mais próximo de Babai. Eles provam que, para geradores de anel curtos, o vetor alvo reside dentro do "raio de captura" do reticulado, permitindo que o algoritmo de Babai recupere a discrepância de unidade exatamente.
4. Recuperação do Gerador Curto: A unidade $\epsilon$ é reconstruída a partir da solução do CVP, e o gerador curto é recuperado como $g_0 = g \cdot \epsilon^{-1}$.

Principais Contribuições

• PIP Quântico de Tempo Polinomial: O artigo fornece a primeira construção de um algoritmo quântico de tempo polinomial para o PIP sobre anéis ciclotômicos de potência de 2. A complexidade é de $O(n^3 \log^2 n)$ portas quânticas e $O(n^2 \log n)$ qubits, onde $n$ é o grau do anel. Isso remove a sobrecarga exponencial anteriormente associada ao algoritmo de Biasse-Song.
• Análise de Fator de Aproximação Ajustada: Os autores derivam um fator de aproximação exato $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$. Eles provam que a variância $\sigma_d$ da imersão logarítmica é $O(1)$ e independente do módulo $q$.
• Verificação do Número de Classes: O trabalho depende da prova (da Parte I) de que o número de classes do subcorpo real máximo é trivial ($h^+_k = 1$) para todo $k \le 12$, garantindo que todo ideal seja principal.
• Extensão para Múltiplos Esquemas: O framework é estendido além do ML-KEM para analisar variantes do Falcon, Hawk e NTRU sobre anéis ciclotômicos de potência de 2, demonstrando que as mesmas fraquezas algébricas se aplicam.

Resultados
Os autores fornecem estimativas de segurança concretas para conjuntos de parâmetros padronizados:

• ML-KEM-1024: O ataque alcança um fator de aproximação mediano $\gamma_{med} \approx 21$ e um fator do percentil 99 $\gamma_{99\%} \approx 103$. Ambos os valores estão significativamente abaixo do limiar de segurança de $q/2 = 1665$. A probabilidade de sucesso é estimada em $\ge 0,99$ para $d \le 3$ e $\ge 0,90$ para $d=4$, com probabilidade de falha reduzível para $< 10^{-6}$ via repetição.
• Estimativas de Recursos: Para ML-KEM-1024 ($n=256$), o ataque requer aproximadamente $2^{27}$ portas lógicas e $1,4 \times 10^6$ qubits físicos (assumindo código de superfície com distância 30).
• Outros Esquemas:
  • Falcon: O ataque quebra Falcon-512 e Falcon-1024 com margens de $72\times$ e $63\times$, respectivamente.
  • Hawk: O ataque quebra Hawk-512 e Hawk-1024. Hawk-256 é condicionalmente quebrado; embora o limite formal de 99% exceda o limiar, simulações empíricas mostram uma taxa de sucesso de 99,99%.
  • NTRU: O ataque aplica-se às variantes NTRU-HPS e NTRU-HRSS sobre anéis ciclotômicos de potência de 2, alcançando margens que variam de $11\times$ a $45\times$.

Significado e Alegações
O artigo afirma resolver as questões abertas sobre o ataque CDPR demonstrando que:

1. O fator de aproximação é pequeno o suficiente para quebrar todos os conjuntos de parâmetros padronizados de ML-KEM, Falcon, Hawk e NTRU sobre anéis ciclotômicos de potência de 2 sob um ataque quântico.
2. O PIP pode ser resolvido em tempo polinomial verdadeiro ($O(n^3 \log^2 n)$) sem fatores exponenciais ocultos ou dependência de conjecturas de teoria dos números não provadas como a GRH.
3. A estrutura algébrica dos anéis ciclotômicos de potência de 2 permite que um adversário quântico reduza o fator de aproximação de superpolinomial ($\approx 2^{54}$ em estimativas anteriores) para subpolinomial ($\approx 2^{21}$), quebrando efetivamente as suposições de segurança desses candidatos pós-quânticos.

Os autores observam que, embora o ataque seja probabilístico, a probabilidade de falha é baixa e pode ser mitigada por repetições independentes. Eles enfatizam que os resultados dependem das propriedades algébricas específicas dos anéis ciclotômicos de potência de 2 e da trivialidade do número de classes para $k \le 12$.