# SALSA PICANTE: a machine learning attack on LWE with binary secrets

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 7 Mar 2023.

## Builds on (most cited first, 17 of 17)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Transformer-based Acoustic Modeling for Hybrid Speech Recognition](https://mlsanity.com/paper/1910.09799/) (2019)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [Classical Hardness of Learning with Errors](https://mlsanity.com/paper/1306.0281/) (2013)

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

- [Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors](https://mlsanity.com/paper/2402.01082/) (2024)
- [Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic](https://mlsanity.com/paper/2410.03569/) (2024)
- [Geometric Generality of Transformer-Based Gr"obner Basis Computation](https://mlsanity.com/paper/2504.12465/) (2025)
- [Machine learning for modular multiplication](https://mlsanity.com/paper/2402.19254/) (2024)
- [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)
- [NoMod: A Non-modular Attack on Module Learning With Errors](https://mlsanity.com/paper/2510.02162/) (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 underpinning many proposed post-quantum cryptographic (PQC) systems. The only PQC Key Exchange Mechanism (KEM) standardized by NIST is based on module~LWE, and current publicly available PQ Homomorphic Encryption (HE) libraries are based on ring LWE. The security of LWE-based PQ cryptosystems is critical, but certain implementation choices could weaken them. One such choice is sparse binary secrets, desirable for PQ HE schemes for efficiency reasons. Prior work, SALSA, demonstrated a machine learning-based attack on LWE with sparse binary secrets in small dimensions (n ≤ 128) and low Hamming weights (h ≤ 4). However, this attack assumes access to millions of eavesdropped LWE samples and fails at higher Hamming weights or dimensions. We present PICANTE, an enhanced machine learning attack on LWE with sparse binary secrets, which recovers secrets in much larger dimensions (up to n=350) and with larger Hamming weights (roughly n/10, and up to h=60 for n=350). We achieve this dramatic improvement via a novel preprocessing step, which allows us to generate training data from a linear number of eavesdropped LWE samples (4n) and changes the distribution of the data to improve transformer training. We also improve the secret recovery methods of SALSA and introduce a novel cross-attention recovery mechanism allowing us to read off the secret directly from the trained models. While PICANTE does not threaten NIST's proposed LWE standards, it demonstrates significant improvement over SALSA and could scale further, highlighting the need for future investigation into machine learning attacks on LWE with sparse binary secrets.