Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

1. Problem Statement

The paper addresses the Learning With Errors (LWE) problem, a foundational hard mathematical problem underpinning many Post-Quantum Cryptography (PQC) systems. Specifically, the authors investigate the vulnerability of LWE instances with small and sparse secrets (binary, ternary, or small integer vectors) to Machine Learning (ML) attacks.

• The Challenge: Previous ML attacks (e.g., SALSA, PICANTE, VERDE) using Transformer models could successfully recover secrets only when the number of non-zero bits in the "cruel region" (the unreduced part of the secret vector after lattice reduction) was limited to 3 or fewer.
• The Bottleneck: As the Hamming weight (number of non-zero bits) of the secret increases, the "cruel region" often contains more than 3 active bits. The dot product $a \cdot s$ grows large, causing the modular arithmetic to wrap around the modulus $q$ multiple times. Transformers struggle to learn these complex modular additions, causing ML attacks to fail for denser secrets.
• The Goal: To extend ML attacks to recover secrets with significantly higher Hamming weights and more "cruel bits" (up to 8) by overcoming the limitations of current model architectures and training strategies.

2. Methodology

The authors propose a three-pronged approach to enhance ML-based secret recovery:

A. Large Training Sets and Data Repetition

• Hypothesis: Inspired by prior work showing that Transformers learn modular arithmetic better when trained on repeated examples (rather than unique samples), the authors hypothesized that scaling up the dataset and repeating examples would help models learn the complex modular dot products required for denser secrets.
• Implementation: They generated massive datasets (up to 400 million reduced LWE pairs). Crucially, they explored data repetition, where the same unique examples are repeated multiple times ($R$) during training.
• Synthetic Data: To bypass the high computational cost of BKZ lattice reduction (which takes ~1 minute per pair on a CPU), they generated synthetic reduced vectors that mimic the statistical properties (variance and distribution) of BKZ-reduced data. They verified that models trained on synthetic data perform equivalently to those trained on real BKZ-reduced data.

B. Stepwise Regression for "Cool Bits"

• Context: In reduced LWE, the secret vector is split into the cruel region (unreduced, hard to learn) and the cool region (reduced, easier to learn). Previous methods used standard linear regression to recover cool bits once the cruel bits were guessed.
• Critique of Linear Regression: The authors argue linear regression is suboptimal because:
  1. It assumes feature correlation (which doesn't exist in LWE matrices).
  2. It ignores the modular nature of the dot product, leading to underestimation of non-zero bits due to "wrapping."
• New Technique: They introduced Stepwise Regression (and its dual variant).
  • Process: Instead of solving for all bits at once, the algorithm iteratively identifies the feature with the lowest contribution and assigns it a value of zero (exploiting sparsity).
  • Dual Stepwise: Once the remaining bits are mostly non-zero (ones), the algorithm flips the problem (dual) to solve for the remaining zeros. This iterative elimination avoids error accumulation from modular arithmetic.

C. Model Architecture Enhancements

• Transformer: An encoder-only Transformer (4 layers) with angular embeddings (mapping integers to the unit circle) was used.
• Positional Embeddings: A novel binary embedding was added to the input to explicitly indicate whether a coordinate belongs to the "cruel" or "cool" region, improving the model's ability to distinguish and recover bits in the difficult region.

3. Key Contributions

1. Breaking the "3-Cruel-Bit" Barrier: The authors successfully recovered secrets with up to 8 cruel bits, a significant improvement over the previous limit of 3.
2. Data Repetition Scaling Law: They established an empirical power-law relationship between the number of model-based attempts ($A$), total training data ($D$), and repetition factor ($R$):
   $$\ln(AR) = C_R - \alpha_R \ln(D)$$
   They found that repetition ($R$) not only reduces the need for distinct data but fundamentally reshapes the scaling law, making repeated data crucial for high-Hamming-weight recovery.
3. Stepwise Regression for Cool Bits: Replaced linear regression with stepwise regression, demonstrating superior performance in recovering the "cool" portion of the secret, especially in high-reduction settings.
4. Synthetic Data Validation: Proved that synthetic data can effectively replace expensive BKZ-reduced data for training and scaling law analysis, drastically reducing the computational cost of experimentation.

4. Experimental Results

The authors tested four LWE settings with varying dimensions ($n$) and moduli ($q$). Key results include:

• Hamming Weight Recovery:
  • Binary Secrets: Recovered secrets with Hamming weights up to 75 (for $n=512, \log_2 q=41$) and 70 (for $n=256, \log_2 q=20$).
  • Comparison: This vastly outperforms prior ML attacks (e.g., VERDE recovered $h=63$ for $n=512$) and non-ML "Cool & Cruel" attacks.
• Recovery Rates:
  • For $n=256, \log_2 q=20$ and $h=33$, their method recovered 98% of secrets, whereas VERDE recovered only 33%.
  • For $n=512, \log_2 q=41$ and $h=63$, their method recovered 91%, compared to 15% for VERDE.
• Data Efficiency:
  • For $n=512, \log_2 q=28$, secrets with 4 cruel bits were recovered using only 20 million examples with 10x repetition, whereas previous methods required much larger budgets or failed entirely.
• Scaling Findings: Increasing model parameters (layers/embedding size) did not significantly improve performance. The primary driver of success was data volume and repetition, not model complexity.

5. Significance and Implications

• Security Assessment: The results suggest that LWE-based PQC systems using sparse secrets may be less secure than previously thought when facing advanced ML attacks. The "cruel region" limitation is not a hard barrier but a function of data availability and training strategy.
• Methodological Shift: The paper demonstrates that for specific cryptographic tasks involving modular arithmetic, data repetition and iterative statistical methods (stepwise regression) are more effective than simply scaling model size.
• Future Research: The work provides a framework for estimating the security of LWE parameters against ML attacks using scaling laws. It also highlights the potential of using synthetic data to simulate attacks without the prohibitive cost of lattice reduction, allowing for faster evaluation of PQC standards.
• Limitations: The attack currently targets basic LWE with sparse binary/ternary secrets. While adaptable to Ring/Module LWE, the high computational cost of generating BKZ-reduced data (though mitigated by synthetic data) remains a practical constraint for real-world attacks with massive datasets.

In conclusion, this paper demonstrates that the limitations of ML attacks on LWE are not inherent to the models but to the training data strategy. By leveraging massive repeated datasets and stepwise regression, the authors have significantly expanded the boundary of recoverable secret complexity.