SALSA: Attacking Lattice Cryptography with Transformers

Emily Wenger; Mingjie Chen; Francois Charton; Kristin Lauter

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 cryptography cryptanalysis LWE Machine 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}
}