Paper 2022/935
SALSA: Attacking Lattice Cryptography with Transformers
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
-
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}
}