Predicting Module-Lattice Reduction

Resumo Técnico: Predizendo a Redução de Lattices Modulares

Enunciado do Problema
O artigo aborda uma questão crítica na criptoanálise de esquemas criptográficos baseados em lattices modulares (como os padrões NIST ML-KEM, ML-DSA e FN-DSA): a redução de lattice modular (especificamente o module-BKZ) é mais ou menos eficiente do que a redução de lattice não estruturada (BKZ) quando fornecida o mesmo oráculo de Problema do Vetor Mais Curto (SVP)?

Embora trabalhos teóricos fundamentais tenham estabelecido a existência de variantes modulares de LLL e algoritmos de redução por blocos, eles focaram no comportamento assintótico de pior caso. Uma preocupação específica, destacada como "Q8" na submissão do Kyber ao NIST, postula que a estrutura algébrica de lattices modulares sobre corpos ciclotômicos pode permitir acelerações (por exemplo, um fator de $d$ para $d^2$) ou, inversamente, pode degradar a qualidade da base reduzida em comparação com o BKZ não estruturado. O artigo visa fornecer uma análise concreta de caso médio para responder se o module-BKZ oferece um ganho ou uma perda em termos do tamanho de bloco $\beta$ necessário para atingir uma determinada qualidade de base (inclinação/slope).

Metodologia
Os autores empregam uma análise baseada em heurísticas apoiada por experimentos extensos para prever a "inclinação" (slope) do perfil da base após a execução do module-BKZ. A inclinação é definida como a taxa de decaimento nas normas logarítmicas dos vetores ortogonalizados de Gram-Schmidt.

1. Implementação Experimental: Os autores desenvolveram a primeira implementação de código aberto de module-BKZ para corpos ciclotômicos (até condutor 16), utilizando as bibliotecas existentes fplll e G6K. Eles abordaram desafios técnicos relativos à preservação da estrutura modular durante a redução de tamanho e ao uso de um "embedding cíclico" para garantir que o produto interno de traço seja compatível com bibliotecas padrão de redução de lattice inteira.
2. Modelagem Teórica (Module-Lattice GSA): Eles estendem a Suposição da Série Geométrica (GSA), comumente usada para BKZ não estruturado, para lattices modulares. Isso envolve modelar o $K$-perfil esperado (em média sobre o grau $d$ do corpo numérico) de uma base reduzida.
3. Decomposição da Inclinação: A inclinação prevista do module-BKZ é decomposta em quatro termos distintos ($t_1$ a $t_4$) que impulsionam o desvio do BKZ não estruturado:
   • $t_1$ (Heurística Gaussiana): O comprimento esperado do vetor mais curto em um lattice modular aleatório, ajustado para o número de raízes da unidade ($\mu_K$).
   • $t_2$ (Gap do Discriminante): Um termo dependente do discriminante $\Delta_K$ do corpo numérico $K$.
   • $t_3$ (Gap de Skewness/Assimetria): Mede o desvio da norma algébrica do vetor em relação à sua norma euclidiana (assimetria do vetor através das imersões/embeddings).
   • $t_4$ (Gap de Índice): Leva em conta o índice do ideal gerado pelo vetor mais curto dentro do módulo.
4. Análise Assintótica: Os autores derivam uma fórmula assintótica para o "tamanho de bloco equivalente" $\beta_{eq}$ necessário para que o module-BKZ iguale a inclinação do BKZ não estruturado com bloco $\beta$.

Principais Contribuições e Resultados

• Predição Quantitativa da Inclinação: O artigo fornece uma fórmula concreta que prevê a inclinação do module-BKZ como uma função do tamanho do bloco $\beta$, do grau do corpo $d$ e do discriminante do corpo $\Delta_K$.
• O Discriminante como Impulsionador: A análise identifica o discriminante $\Delta_K$ como a principal quantidade que impulsiona a diferença de desempenho. Especificamente, o termo $\ln(|\Delta_K|/d^d)$ determina se o module-BKZ ganha ou perde eficiência.
• Ganho/Perda de Tamanho de Bloco Assintótico: Os autores derivam a seguinte relação assintótica para o tamanho de bloco equivalente $\beta_{eq}$:
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • Campos Ciclotômicos de Potência de Dois: Para campos onde o condutor é uma potência de dois (relevante para os atuais padrões NIST), $|\Delta_K| = d^d$. Consequentemente, o termo logarítmico desaparece, e o custo é dominado pelo termo linear $d-1$. Isso implica que o module-BKZ requer um tamanho de bloco maior em aproximadamente $d-1$ para atingir a mesma inclinação que o BKZ não estruturado. Isso confirma e quantifica a preocupação levantada no Q8 do Kyber, sugerindo uma leve penalidade de desempenho em vez de uma aceleração.
  • Outros Campos Ciclotômicos: Para campos com fatores primos ímpares em seu condutor (por exemplo, condutores da forma $2^i \cdot 3^j$), $|\Delta_K| < d^d$. Nesses casos, o termo logarítmico é negativo, resultando em um ganho sublinear no tamanho de bloco requerido ($\Theta(\beta / \ln \beta)$). Isso se traduz em uma aceleração subexponencial na complexidade do ataque.
• Validação Experimental: Os dados experimentais dos autores em vários campos ciclotômicos ($\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$) alinham-se bem com suas previsões. Os dados confirmam que $\mathbb{Q}(\omega_3)$ e $\mathbb{Q}(\omega_{15})$ exibem perfis mais planos (melhor redução) comparados à linha de base não estruturada, enquanto $\mathbb{Q}(\omega_{16})$ (potência de dois) mostra um perfil pior.

Significância e Alegações
O artigo afirma ser o primeiro trabalho a fornecer uma análise concreta de caso médio de module-BKZ, indo além dos limites teóricos de pior caso. Sua significância reside em:

1. Resolvendo o Q8: Ele aborda diretamente a questão aberta sobre a eficiência do module-BKZ em campos ciclotômicos de potência de dois, concluindo que, para esses campos específicos, a estrutura modular não proporciona uma aceleração sobre o BKZ não estruturado; na verdade, incorre em um pequeno overhead (exigindo um tamanho de bloco maior).
2. Identificando Construções Alternativas: Destaca que esquemas de lattice modular usando condutores com pequenos fatores primos ímpares (por exemplo, 3, 5) podem ser significativamente mais fracos do que o previamente pensado, pois a estrutura algébrica fornece uma aceleração subexponencial para ataques de redução de lattice.
3. Ferramental Prático: Ao fornecer a primeira implementação de código aberto de module-BKZ, os autores permitem maiores experimentações e estimativas de segurança para esquemas de lattice modular.

Os autores mantêm-se modestos quanto às suas alegações, observando que sua análise depende de heurísticas (como a Suposição da Série Geométrica adaptada para módulos) e que lacunas permanecem na modelagem de fenômenos de "cabeça e cauda" (head and tail) e na velocidade de convergência do algoritmo. Eles declaram explicitamente que seus resultados ainda não fornecem um custo preciso para ataques específicos, mas sim um framework preditivo para a inclinação da base reduzida.