Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

Resumo Técnico: Melhorando Ataques de ML no LWE com Repetição de Dados e Regressão Passo a Passo

1. O Problema: Vulnerabilidades no Aprendizado com Erros (LWE)

O problema de Aprendizado com Erros (Learning With Errors - LWE) é a base matemática de muitos sistemas de criptografia pós-quântica (PQC). A segurança do LWE depende da dificuldade de recuperar um vetor secreto $s$ a partir de pares $(a, b)$, onde $b = a \cdot s + \epsilon \pmod q$, sendo $\epsilon$ um ruído pequeno.

Embora o LWE seja considerado seguro para vetores secretos densos e grandes, variantes com secrets esparsos (poucos bits não nulos) ou pequenos (valores binários, ternários ou inteiros pequenos) são atraentes para eficiência em criptografia homomórfica. Ataques anteriores baseados em Machine Learning (ML), como o SALSA, demonstraram sucesso na recuperação de secretos com até 3 bits "ativos" em regiões específicas do vetor, mas falhavam em secretos mais densos ou com maior peso de Hamming ($h$).

Um obstáculo principal identificado na literatura recente é a divisão do vetor secreto em duas regiões após a redução de rede (BKZ):

• Região Cruel (Cruel Region): As primeiras $c$ coordenadas que permanecem não reduzidas. O modelo de ML luta para aprender o produto escalar modular quando o número de bits não nulos nesta região excede 3.
• Região Fresca (Cool Region): As coordenadas restantes, que são reduzidas e, teoricamente, mais fáceis de recuperar uma vez que a região cruel é conhecida.

O trabalho anterior limitava-se a recuperar secretos com no máximo 3 bits na região cruel. Este artigo visa superar essa barreira.

2. Metodologia

Os autores propõem uma abordagem combinada que envolve três pilares principais:

A. Conjuntos de Dados Maiores e Repetição de Exemplos

• Hipótese: Modelos de ML (Transformers) têm dificuldade em aprender adição modular quando o produto escalar é grande. A repetição de exemplos de treinamento ajuda o modelo a generalizar melhor essa operação.
• Execução: Os autores geraram conjuntos de dados massivos (até 400 milhões de pares LWE reduzidos). Eles treinaram modelos em dados reais (reduzidos via BKZ) e dados sintéticos (gerados para simular a distribuição de variância dos dados reduzidos).
• Repetição: Em vez de apenas aumentar o tamanho do conjunto de dados único, eles repetiram os mesmos exemplos várias vezes durante o treinamento (fatores de repetição de 1x a 50x), observando que isso é crucial para a recuperação de bits na região cruel.

B. Arquitetura do Modelo

• Utilizam um Transformer apenas com codificador (encoder-only) com 4 camadas.
• Embeddings Angulares: As entradas são mapeadas para o espaço complexo ($\cos, \sin$) para lidar com a aritmética modular.
• Novo Embedding de Posição: Introduzem um embedding binário que indica se uma coordenada pertence à região "cruel" ou "fresca", melhorando a capacidade do modelo de distinguir e recuperar os bits da região cruel.

C. Recuperação de Bits "Frescos" via Regressão Passo a Passo (Stepwise Regression)

• Problema do Método Anterior: Métodos anteriores usavam regressão linear simples para recuperar os bits da região fresca após adivinhar os bits da região cruel. Isso falhava porque a regressão linear ignora a natureza modular (o produto pode "envolver" o módulo $q$) e acumula erros devido à inversão de matrizes de covariância.
• Solução Proposta:
  1. Subtrai-se a contribuição dos bits da região cruel (já adivinhados) de $b$.
  2. Aplica-se Regressão Passo a Passo (Stepwise Regression): O algoritmo identifica iterativamente o bit com a menor contribuição (assumindo que é zero) e o remove do conjunto de equações.
  3. Regressão Dual: Quando a maioria dos bits restantes são uns (em vez de zeros), o algoritmo inverte o problema (dual) para continuar a eliminação eficiente.
  4. Isso permite recuperar bits "frescos" de forma mais robusta, explorando a esparsidade do segredo.

3. Contribuições Principais

1. Superação do Limite de 3 Bits Cruéis: Demonstraram que, com grandes conjuntos de dados e repetição, é possível recuperar secretos com até 8 bits na região cruel (região não reduzida), superando o limite anterior de 3.
2. Técnica de Regressão Passo a Passo: Substituíram a regressão linear padrão por regressão passo a passo (e sua variante dual) para a recuperação dos bits da região fresca, aumentando drasticamente a taxa de sucesso.
3. Dados Sintéticos e Escalabilidade: Geraram 400 milhões de amostras sintéticas, provando que dados sintéticos com a mesma variância coordenada que os dados reduzidos por BKZ produzem resultados equivalentes. Isso reduz o custo computacional de experimentos futuros.
4. Lei de Escala Empírica: Definiram uma lei de potência empírica relacionando o número de tentativas de recuperação ($A$) com o tamanho do conjunto de dados ($D$) e a repetição ($R$):
   $$\ln(AR) = C_R - \alpha_R \ln(D)$$
   Eles descobriram que a repetição de dados não apenas reduz a necessidade de amostras distintas, mas altera fundamentalmente a lei de escala, tornando-se essencial para recuperar secretos de alto peso de Hamming.

4. Resultados

Os autores testaram quatro configurações de parâmetros LWE ($n=256/512$, diferentes $\log_2 q$). Os resultados superaram significativamente o estado da arte (SALSA, VERDE, C&C):

• Peso de Hamming Máximo Recuperado:
  • Para $n=256, \log_2 q = 20$: Recuperaram $h=70$ (vs. $h=33$ do VERDE).
  • Para $n=512, \log_2 q = 41$: Recuperaram $h=75$ (vs. $h=63$ do VERDE e $h=60$ do C&C).
• Taxa de Recuperação Esperada:
  • Para $n=256, h=33$: O método anterior (VERDE) recuperava 33% dos secretos; o novo método recupera 98%.
  • Para $n=512, h=63$: O método anterior recuperava 15%; o novo método recupera 91%.
• Eficiência de Dados: A repetição de dados (ex: 15x a 50x) mostrou-se mais eficaz do que apenas aumentar o tamanho do conjunto de dados único para a recuperação de bits na região cruel.

5. Significado e Conclusão

Este trabalho tem implicações profundas para a segurança da criptografia pós-quântica:

• Reavaliação de Segurança: Mostra que os limites de segurança para secretos esparsos e pequenos em esquemas baseados em LWE são mais baixos do que se pensava anteriormente. Ataques baseados em ML podem ser escalados para quebrar instâncias que eram consideradas seguras.
• Importância da Esparsidade: Reforça que a esparsidade do segredo é uma vulnerabilidade crítica, especialmente quando combinada com técnicas de redução de rede (BKZ).
• Custo Computacional vs. ML: Embora o ataque exija grandes recursos computacionais para gerar dados (ou usar dados sintéticos), ele demonstra que o ML pode superar ataques clássicos de força bruta em certos regimes de parâmetros.
• Direção Futura: A descoberta de que dados sintéticos são suficientes para treinar esses modelos sugere que a comunidade de segurança pode usar simulações baratas para testar a robustez de novos esquemas criptográficos antes da padronização.

Em resumo, o artigo demonstra que a combinação de grandes volumes de dados repetidos e técnicas estatísticas avançadas (regressão passo a passo) permite que modelos de ML superem as barreiras de aprendizado modular, recuperando secretos LWE com pesos de Hamming e complexidade anteriormente considerados inatingíveis por métodos baseados em ML.