These labels were automatically added by AI and may be inaccurate. For details, see About Literature Database.
Abstract
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.