Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

• URL: http://arxiv.org/abs/2604.03903v1
• Date: Sun, 05 Apr 2026 00:15:04 GMT
• Title: Improving ML Attacks on LWE with Data Repetition and Stepwise Regression
• Abstract summary: The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography.<n>Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets.<n>We show that using larger training sets and repeated examples enables recovery of denser secrets.
• Score: 18.872311974918322
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography. In the simplest case of binary secrets, it is the subset sum problem, with error. Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets, succeeding on fairly sparse secrets. The ML attacks recover secrets with up to 3 active bits in the "cruel region" (Nolte et al., 2024) on samples pre-processed with BKZ. We show that using larger training sets and repeated examples enables recovery of denser secrets. Empirically, we observe a power-law relationship between model-based attempts to recover the secrets, dataset size, and repeated examples. We introduce a stepwise regression technique to recover the "cool bits" of the secret.

Related papers

• NoMod: A Non-modular Attack on Module Learning With Errors [16.228565693406576]
  Quantum computing threatens classical public-key cryptography.<n>We present NoMod ML-Attack, a hybrid white-box cryptanalytic method.<n>We release our implementation in an anonymous repository.
  arXiv  Detail & Related papers  (2025-10-02T16:12:13Z)
• Nudging the Boundaries of LLM Reasoning [77.26972440427285]
  Current online reinforcement learning algorithms cannot learn from problems that are "unsolvable" to the model.<n>We propose NuRL, a "nudging" method that aims to push the upper bound of LLM reasoning using self-generated hints.<n>NuRL achieves consistent improvements across 6 benchmarks and 3 models, while remaining complementary to test-time scaling.
  arXiv  Detail & Related papers  (2025-09-30T02:01:40Z)
• Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic [30.93087957720688]
  We develop techniques that significantly boost the performance of ML models on modular arithmetic tasks.<n>Our core innovation is the use of custom training data distributions and a carefully designed loss function.<n>Our techniques also help ML models learn other well-studied problems better, including copy, associative recall, and parity.
  arXiv  Detail & Related papers  (2024-10-04T16:19:33Z)
• From Theft to Bomb-Making: The Ripple Effect of Unlearning in Defending Against Jailbreak Attacks [85.84979847888157]
  Large Language Models (LLMs) are known to be vulnerable to jailbreak attacks.<n>LLMs can implicitly unlearn harmful knowledge that was not explicitly introduced during the unlearning phase.<n>We empirically validate this phenomenon, which makes unlearning-based methods able to decrease the Attack Success Rate.
  arXiv  Detail & Related papers  (2024-07-03T07:14:05Z)
• Enabling High-Sparsity Foundational Llama Models with Efficient Pretraining and Deployment [56.44025052765861]
  Large language models (LLMs) have revolutionized Natural Language Processing (NLP), but their size creates computational bottlenecks. We introduce a novel approach to create accurate, sparse foundational versions of performant LLMs. We show a total speedup on CPUs for sparse-quantized LLaMA models of up to 8.6x.
  arXiv  Detail & Related papers  (2024-05-06T16:03:32Z)
• FFN-SkipLLM: A Hidden Gem for Autoregressive Decoding with Adaptive Feed Forward Skipping [49.66872823080736]
  Autoregressive Large Language Models (e.g., LLaMa, GPTs) are omnipresent achieving remarkable success in language understanding and generation. To mitigate overload incurred during generation, several early-exit and layer-dropping strategies have been proposed. We propose FFN-SkipLLM, which is an input-adaptive feed-forward skipping strategy.
  arXiv  Detail & Related papers  (2024-04-05T02:35:43Z)
• The cool and the cruel: separating hard parts of LWE secrets [11.000531626756853]
  Known attacks on sparse binary LWE secrets include the sparse dual attack and the hybrid sparse dual-meet in the middle attack. In this paper, we provide a new statistical attack with low memory requirement.
  arXiv  Detail & Related papers  (2024-03-15T14:16:21Z)
• Alpaca against Vicuna: Using LLMs to Uncover Memorization of LLMs [61.04246774006429]
  We introduce a black-box prompt optimization method that uses an attacker LLM agent to uncover higher levels of memorization in a victim agent.<n>We observe that our instruction-based prompts generate outputs with 23.7% higher overlap with training data compared to the baseline prefix-suffix measurements.<n>Our findings show that instruction-tuned models can expose pre-training data as much as their base-models, if not more so, and using instructions proposed by other LLMs can open a new avenue of automated attacks.
  arXiv  Detail & Related papers  (2024-03-05T19:32:01Z)
• Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors [10.800552110718714]
  Learning with Errors (LWE) is a hard math problem underlying post-quantum cryptography systems for key exchange and digital signatures. Prior work proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods -- better preprocessing, angular embeddings and model pre-training -- to improve these attacks.
  arXiv  Detail & Related papers  (2024-02-02T00:48:27Z)
• Enhancing Consistency and Mitigating Bias: A Data Replay Approach for Incremental Learning [93.90047628101155]
  Deep learning systems are prone to catastrophic forgetting when learning from a sequence of tasks.<n>To address this, some methods propose replaying data from previous tasks during new task learning.<n>However, it is not expected in practice due to memory constraints and data privacy issues.
  arXiv  Detail & Related papers  (2024-01-12T12:51:12Z)
• SALSA PICANTE: a machine learning attack on LWE with binary secrets [8.219373043653507]
  We present PICANTE, an enhanced machine learning attack on LWE with sparse binary secrets. PICANTE recovers secrets in much larger dimensions (up to $n=350$) and with larger Hamming weights. While PICANTE does not threaten NIST's proposed LWE standards, it demonstrates significant improvement over SALSA.
  arXiv  Detail & Related papers  (2023-03-07T19:01:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.