# SALSA: Attacking Lattice Cryptography with Transformers

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 72 references that are in the map.
- First posted on arXiv 11 Jul 2022.

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

- [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)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Neural Symbolic Regression that Scales](https://mlsanity.com/paper/2106.06427/) (2021)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Neural Arithmetic Logic Units](https://mlsanity.com/paper/1808.00508/) (2018)
- [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)
- [Deep Symbolic Regression for Recurrent Sequences](https://mlsanity.com/paper/2201.04600/) (2022)
- [Symbolic Brittleness in Sequence Models: on Systematic Generalization in Symbolic Mathematics](https://mlsanity.com/paper/2109.13986/) (2021)
- [Classical Hardness of Learning with Errors](https://mlsanity.com/paper/1306.0281/) (2013)
- [Can Sequence-to-Sequence Models Crack Substitution Ciphers?](https://mlsanity.com/paper/2012.15229/) (2020)
- [Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis](https://mlsanity.com/paper/2107.07116/) (2021)
- [Solving Arithmetic Word Problems with Transformers and Preprocessing of Problem Text](https://mlsanity.com/paper/2106.00893/) (2021)
- [A deep language model to predict metabolic network equilibria](https://mlsanity.com/paper/2112.03588/) (2021)
- [Provably weak instances of Ring-LWE](https://mlsanity.com/paper/1502.03708/) (2015)
- [Learning the Enigma with Recurrent Neural Networks](https://mlsanity.com/paper/1708.07576/) (2017)
- [Using fuzzy bits and neural networks to partially invert few rounds of some cryptographic hash functions](https://mlsanity.com/paper/1901.02438/) (2019)
- [Security considerations for Galois non-dual RLWE families](https://mlsanity.com/paper/1710.03316/) (2017)
- [Attacks on the Search-RLWE problem with small errors](https://mlsanity.com/paper/1710.03739/) (2017)

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

- [Formal Mathematical Reasoning: A New Frontier in AI](https://mlsanity.com/paper/2412.16075/) (2024)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers](https://mlsanity.com/paper/2410.08304/) (2024)
- [Transforming the Bootstrap: Using Transformers to Compute Scattering Amplitudes in Planar N = 4 Super Yang-Mills Theory](https://mlsanity.com/paper/2405.06107/) (2024)
- [SALSA PICANTE: a machine learning attack on LWE with binary secrets](https://mlsanity.com/paper/2303.04178/) (2023)
- [Learning to Compute Gr"obner Bases](https://mlsanity.com/paper/2311.12904/) (2023)
- [Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors](https://mlsanity.com/paper/2402.01082/) (2024)
- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [Should LLM Safety Be More Than Refusing Harmful Instructions?](https://mlsanity.com/paper/2506.02442/) (2025)
- [Benchmarking Large Language Models for Cryptanalysis and Side-Channel Vulnerabilities](https://mlsanity.com/paper/2505.24621/) (2025)
- [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)
- [Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic](https://mlsanity.com/paper/2310.12660/) (2023)
- [Machine learning for modular multiplication](https://mlsanity.com/paper/2402.19254/) (2024)
- [Local Look-Ahead Guidance via Verifier-in-the-Loop for Automated Theorem Proving](https://mlsanity.com/paper/2503.09730/) (2025)
- [Discovering Learning-Friendly Generation Orders for Sequential Computation](https://mlsanity.com/paper/2506.23875/) (2025)
- [Practically Solving LPN in High Noise Regimes Faster Using Neural Networks](https://mlsanity.com/paper/2303.07987/) (2023)
- [Memorization for Good: Encryption with Autoregressive Language Models](https://mlsanity.com/paper/2305.10445/) (2023)
- [Prime Convolutional Model: Breaking the Ground for Theoretical Explainability](https://mlsanity.com/paper/2503.02773/) (2025)
- [The informativeness of the gradient revisited](https://mlsanity.com/paper/2505.22158/) (2025)
- [CALT: A Library for Computer Algebra with Transformer](https://mlsanity.com/paper/2506.08600/) (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)
- [Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability](https://mlsanity.com/paper/2510.26792/) (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)
- [CARTS: Contextual Autoregressive Rank Transcoding Steganography for Full-Capacity Keyed Text Encoding](https://mlsanity.com/paper/2609.10744/) (2026)

## Abstract (arXiv)

Currently deployed public-key cryptosystems will be vulnerable to attacks by full-scale quantum computers. Consequently, "quantum resistant" cryptosystems are in high demand, and lattice-based cryptosystems, based on a hard problem known as Learning With Errors (LWE), have emerged as strong contenders for standardization. In this work, we train transformers to perform modular arithmetic and combine half-trained models with statistical cryptanalysis techniques to propose SALSA: a machine learning attack on LWE-based cryptographic schemes. SALSA can fully recover secrets for small-to-mid size LWE instances with sparse binary secrets, and may scale to attack real-world LWE-based cryptosystems.