# SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secrets

arXiv: https://arxiv.org/abs/2306.11641 · HTML: https://mlsanity.com/paper/2306.11641/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2023.

## Built on by (most cited first, 8 of 8)

- [Learning to Compute Gr"obner Bases](https://mlsanity.com/paper/2311.12904/) (2023)
- [Geometric Generality of Transformer-Based Gr"obner Basis Computation](https://mlsanity.com/paper/2504.12465/) (2025)
- [Discovering Learning-Friendly Generation Orders for Sequential Computation](https://mlsanity.com/paper/2506.23875/) (2025)
- [The informativeness of the gradient revisited](https://mlsanity.com/paper/2505.22158/) (2025)
- [Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decoding](https://mlsanity.com/paper/2506.20305/) (2025)
- [TAPAS: Datasets for Learning the Learning with Errors Problem](https://mlsanity.com/paper/2510.08797/) (2025)
- [Improving ML Attacks on LWE with Data Repetition and Stepwise Regression](https://mlsanity.com/paper/2604.03903/) (2026)
- [Discovering Lattice Reduction Strategies via Self-Play](https://mlsanity.com/paper/2606.15301/) (2026)

## Abstract (arXiv)

Learning with Errors (LWE) is a hard math problem used in post-quantum cryptography. Homomorphic Encryption (HE) schemes rely on the hardness of the LWE problem for their security, and two LWE-based cryptosystems were recently standardized by NIST for digital signatures and key exchange (KEM). Thus, it is critical to continue assessing the security of LWE and specific parameter choices. For example, HE uses secrets with small entries, and the HE community has considered standardizing small sparse secrets to improve efficiency and functionality. However, prior work, SALSA and PICANTE, showed that ML attacks can recover sparse binary secrets. Building on these, we propose VERDE, an improved ML attack that can recover sparse binary, ternary, and narrow Gaussian secrets. Using improved preprocessing and secret recovery techniques, VERDE can attack LWE with larger dimensions (n=512) and smaller moduli (log2 q=12 for n=256), using less time and power. We propose novel architectures for scaling. Finally, we develop a theory that explains the success of ML LWE attacks.