SALSA FRESCA: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors

Samuel Stevens; Emily Wenger; Cathy Yuanchen Li; Niklas Nolte; Eshika Saxena; Francois Charton; Kristin Lauter

Paper 2024/150

SALSA FRESCA: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors

Samuel Stevens, The Ohio State University

Emily Wenger, Fundamental AI Research (FAIR), Meta

Cathy Yuanchen Li, University of Chicago

Niklas Nolte, Fundamental AI Research (FAIR), Meta

Eshika Saxena, Fundamental AI Research (FAIR), Meta

Francois Charton, Fundamental AI Research (FAIR), Meta

Kristin Lauter, Fundamental AI Research (FAIR), Meta

Abstract

Learning with Errors (LWE) is a hard math problem underlying post-quantum cryptography (PQC) systems for key exchange and digital signatures, recently standardized by NIST. Prior work [Wenger et al., 2022; Li et al., 2023a;b] proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods—better pre-processing, angular embeddings and model pre-training—to improve these attacks, speeding up preprocessing by 25× and improving model sample efficiency by 10×. We demonstrate for the first time that pre-training improves and reduces the cost of ML attacks on LWE. Our architecture improvements enable scaling to larger-dimension LWE problems: this work is the first instance of ML attacks recovering sparse binary secrets in dimension n = 1024, the smallest dimension used in practice for homomorphic encryption applications of LWE where sparse binary secrets are proposed.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: AI4Crypto ML-based attacks Post-Quantum Cryptography LWE lattice-based cryptography
Contact author(s): stevens 994 @ buckeyemail osu edu
ewenger @ meta com
yuanchen @ uchicago edu
nolte @ meta com
eshika @ meta com
fcharton @ meta com
klauter @ meta com
History: 2024-02-02: approved; 2024-02-02: received; See all versions
Short URL: https://ia.cr/2024/150
License: CC BY

BibTeX

@misc{cryptoeprint:2024/150,
      author = {Samuel Stevens and Emily Wenger and Cathy Yuanchen Li and Niklas Nolte and Eshika Saxena and Francois Charton and Kristin Lauter},
      title = {SALSA FRESCA: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2024/150},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/150}},
      url = {https://eprint.iacr.org/2024/150}
}