Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on
  Learning With Errors
Samuel Stevens Emily Wenger Cathy Li Niklas Nolte Eshika Saxena François Charton Kristin Lauter
Learning with Errors (LWE) is a hard math problem underlying recently
standardized post-quantum cryptography (PQC) systems for key exchange and
digital signatures. Prior work 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 preprocessing, angular embeddings and model pre-training
-- to improve these attacks, speeding up preprocessing by $25\times$ and
improving model sample efficiency by $10\times$. 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.