Paper 2022/935

SALSA: Attacking Lattice Cryptography with Transformers

Emily Wenger, University of Chicago
Mingjie Chen, University of Birmingham
Francois Charton, Meta AI
Kristin Lauter, Meta AI, University of Washington

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.

Note: Extended version of work presented at NeurIPS 2022

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. Neural Information Processing Systems (NeurIPS) 2022
Lattice-based cryptographycryptanalysisLWEMachine Learning (ML)
Contact author(s)
ewillson @ uchicago edu
m chen 1 @ bham ac uk
fcharton @ meta com
klauter @ meta com
2023-04-21: revised
2022-07-18: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Emily Wenger and Mingjie Chen and Francois Charton and Kristin Lauter},
      title = {SALSA: Attacking Lattice Cryptography with Transformers},
      howpublished = {Cryptology ePrint Archive, Paper 2022/935},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.