Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

Resumo Técnico: Ataques ao LWE e LPN Esparsos com Novos Trade-offs entre Amostra e Tempo

1. Problema e Contexto

O artigo aborda a análise da complexidade computacional de duas variantes fundamentais de problemas de criptografia pós-quântica: o Learning With Errors (LWE) e o Learning Parity with Noise (LPN), quando submetidos a restrições de esparsidade.

• Definição do Problema: Em vez de vetores de coeficientes aleatórios densos, os vetores de amostra $a \in \mathbb{Z}_q^n$ possuem apenas $k$ entradas não nulas (onde $k \ll n$).
• Motivação: A esparsidade é desejada para melhorar a eficiência em primitivas criptográficas (geração de chaves mais rápida, textos cifrados menores). No entanto, a segurança dessas variantes depende da dificuldade de distinguir entre uma distribuição "plantada" (com um segredo e ruído) e uma distribuição uniforme aleatória.
• Estado da Arte: Trabalhos anteriores (como Wein et al., 2019 e Gupta et al., 2026) desenvolveram métodos eficazes para o caso de módulo $q=2$ (XOR esparsos) utilizando o Método Kikuchi. O trabalho de Jain, Lin e Saha (2024) sugeriu que o LWE esparsos com $k \ge \Omega(\log n)$ e amostras polinomiais seria tão difícil quanto o LWE padrão, mas suas análises de ataques eram limitadas.
• Objetivo do Artigo: Estender o Método Kikuchi para módulos maiores ($q > 2$), fornecendo novos algoritmos e trade-offs precisos entre a complexidade de amostras ($m$) e a complexidade de tempo para distinguir instâncias esparsas de LWE e LPN.

2. Metodologia

Os autores generalizam o Método Kikuchi, originalmente desenvolvido para $q=2$, para o caso de k-LIN$_q$ (sistemas de equações lineares esparsas sobre $\mathbb{Z}_q$). A abordagem central envolve a construção de um Grafo Kikuchi e a aplicação de duas técnicas distintas de análise:

A. Construção do Grafo Kikuchi para $q > 2$

• Transformação: As equações lineares sobre $\mathbb{Z}_q$ são convertidas em equações de produto sobre raízes da unidade complexas ($\Omega_q = \{e^{2\pi i s/q}\}$).
• Espaço de Dimensão Superior: Para lidar com coeficientes e índices simultaneamente, o grafo é construído sobre um espaço de vértices que são subconjuntos de tamanho $l$ de pares (índice, coeficiente), ou seja, $\binom{[n]}{l} \times [q]^l$, onde $k/2 \le l \le n$.
• Estrutura Direcionada: Diferente do caso $q=2$ (grafo não direcionado), para $q>2$, o grafo é direcionado para acomodar a assimetria na diferença generalizada dos coeficientes. Para garantir propriedades espectrais, o grafo é construído de forma que para cada aresta $T \xrightarrow{b} T'$, exista a aresta reversa $T' \xrightarrow{b^*} T$, tornando a matriz de adjacência Hermitiana.

B. Duas Técnicas de Ataque

1. Método Espectral (Generalização de Wein et al.):

   • Ideia: Analisar a norma espectral (o maior autovalor) da matriz de adjacência do Grafo Kikuchi.
   • Lógica:
     • Em uma instância aleatória, a norma espectral esperada é baixa (próxima de 0).
     • Em uma instância plantada, a presença do segredo cria uma correlação que eleva a norma espectral para um valor proporcional à densidade média do grafo ($\Delta$) e à variância do ruído ($\rho$).
   • Técnica: Utiliza a Desigualdade de Bernstein para Matrizes para estabelecer limites de cauda (tail bounds) que separam estatisticamente os dois casos.
   • Vantagens: Funciona para qualquer distribuição de ruído (desde que concentrada em 0) e não requer que $q$ seja primo. Possui uma versão quântica com aceleração.

2. Método de Cobertura $q$-ária (Generalização de Gupta et al.):

   • Ideia: Encontrar "caminhadas fechadas" (closed walks) não triviais no Grafo Kikuchi que correspondam a coberturas $q$-árias (subconjuntos de equações onde a soma dos coeficientes de cada variável é $0 \mod q$).
   • Lógica:
     • Para LPN (ruído uniforme em não-nulos): O produto dos lados direitos das equações na cobertura forma um polinômio multilinear. Os autores provam resultados de anti-concentração para mostrar que o valor esperado desse polinômio é alto no caso plantado e próximo de zero no caso aleatório.
     • Para LWE (ruído Gaussiano limitado): Utiliza-se o fato de que o ruído é limitado. Se $c^T A = 0$, então $c^T \beta = c^T e$. Como $c$ é esparsa (norma $L_1$ pequena), o valor $c^T \beta$ será pequeno no caso plantado, mas uniforme no caso aleatório.
   • Vantagens: Oferece uma aceleração quase quadrática em relação ao método espectral para o mesmo número de amostras. Funciona mesmo que as partes esquerdas das equações não sejam uniformes (caso pior).

3. Contribuições Principais e Resultados

O artigo estabelece novos limites superiores para a complexidade de tempo em função do número de amostras $m$, introduzindo um parâmetro de trade-off $l$.

Teoremas Principais (Informais):

• Para LWE Esparsos (Método Espectral):

  • Tempo: $\tilde{O}\left( \binom{n}{l} q^l \right)$.
  • Amostras necessárias: $m \ge \tilde{O}\left( \binom{n}{l} q^l \right)$ (dependendo da relação entre $q$ e $n$).
  • Funciona para qualquer $q$ e distribuição de ruído adequada.

• Para LWE Esparsos (Método de Cobertura $q$-ária):

  • Tempo: $\tilde{O}\left( q \binom{n}{l} q^l (n/l)^k \right)$.
  • Requer $q$ primo e $q \gg r(l \log n)^{3/2}$.
  • Oferece uma aceleração quase quadrática em relação ao método espectral quando $l \gg k$.

• Para LPN Esparsos:

  • Resultados análogos ao LWE, com tempos de $\tilde{O}\left( \binom{n}{l} q^l \right)$ (espectral) e $\tilde{O}\left( \binom{n}{l} q^l \right)^{1/2+\epsilon} (n/l)^k$ (cobertura).

Análise de Trade-off e Conjectura de Dureza:
Os autores analisam o caso onde o tempo de execução é $2^{\delta n}$ para $\delta > 0$ arbitrariamente pequeno.

• Eles mostram que, se $k = O(\log n / \log \log n)$, amostras polinomiais são suficientes para quebrar o problema em tempo sub-exponencial.
• Se $k = O(\log n)$, são necessárias amostras ligeiramente acima de polinomiais.
• Implicação: Estes resultados validam e apertam a conjectura de Jain, Lin e Saha (2024) sobre a dureza do LWE esparsos. O método Kikuchi fecha a lacuna, mostrando que o problema é tão difícil quanto o LWE padrão apenas sob condições muito específicas de esparsidade e número de amostras, ou que é vulnerável se essas condições forem relaxadas.

4. Significado e Impacto

1. Generalização para Módulos Grandes: O trabalho preenche uma lacuna crítica na literatura, estendendo ataques baseados em grafos (Kikuchi) que eram restritos a $q=2$ para o regime de módulos grandes, essencial para esquemas de criptografia prática como FHE (Homomorphic Encryption).
2. Refinamento da Segurança: Os resultados fornecem limites de segurança mais precisos para primitivas criptográficas que utilizam LWE/LWE esparsos. Eles indicam que a segurança não é absoluta e depende fortemente da escolha dos parâmetros $k$ (esparsidade) e $m$ (número de amostras).
3. Comparação de Métodos: O artigo oferece uma comparação clara entre métodos espectrais e métodos combinatórios (coberturas), destacando que o método de cobertura $q$-ária é superior em termos de tempo para o mesmo número de amostras, embora tenha requisitos mais fortes sobre o módulo $q$ e o ruído.
4. Validação de Conjecturas: Ao demonstrar que o LWE esparsos pode ser resolvido em tempo quase polinomial sob certas condições de amostragem, o trabalho confirma que a conjectura de dureza de JLS24 é "apertada" (tight), ou seja, não há uma margem de segurança oculta significativa além do que foi conjecturado.

Em suma, o papel fornece uma análise de complexidade de granularidade fina para LWE e LPN esparsos, estabelecendo novos padrões para a avaliação de segurança de esquemas criptográficos baseados nesses problemas.