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
Abstract

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

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

BibTeX

@misc{cryptoeprint:2022/935,
      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},
      url = {https://eprint.iacr.org/2022/935}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.