Salsa Picante - a machine learning attack on LWE with binary secrets

Aug 4, 2026

Upload by Logic

Learning With Errors (LWE) underpins many post-quantum cryptography (PQC) proposals, including the NIST-standardized key encapsulation mechanism derived from module LWE and many homomorphic encryption libraries based on ring LWE. Security hinges on correct parameter and implementation choices, and prior attacks showed vulnerabilities for sparse binary secrets only in small dimensions and very low Hamming weights. Picante improves secret recovery to far larger dimensions and higher Hamming weights via preprocessing, efficient training-data generation, and cross-attention recovery, strengthening evidence for further investigation into ML attacks on sparse-binary LWE.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages15

Reading Time38 min

AccessFree to download

Abstract

Introduction

Salsa Picante: a machine learning a􀀝ack on LWE with binary secrets arXiv :2303 .04178v2 [ cs .CR] 9 May 2023 Cathy Li∗ Meta AI Mohmed Malhou Meta AI Jana Sotáková∗ Meta AI Evrard Garcelon ENSAE-CREST Emily Wenger University of Chicago Francois Charton† Meta AI Kristin Lauter† Meta AI ABSTRACT Learning With Errors (LWE) is a hard math problem underpinning many proposed post-quantum cryptographic (PQC) systems. The only PQC Key Exchange Mechanism (KEM) standardized by NIST [13] is based on module LWE, and current publicly available PQ Homomorphic Encryption (HE) libraries are based on ring LWE [2] . The security of LWE-based PQ cryptosystems is critical, but certain implementation choices could weaken them. One such choice is sparse binary secrets, desirable for PQ HE schemes for eﬃciency reasons. Prior work Salsa [49] demonstrated a machine learningbased attack on LWE with sparse binary secrets in small dimensions (􀀽 ≤ 128) and low Hamming weights (ℎ ≤ 4) . However, this attack assumes access to millions of eavesdropped LWE samples and fails at higher Hamming weights or dimensions. We present Picante, an enhanced machine learning attack on LWE with sparse binary secrets, which recovers secrets in much larger dimensions (up to 􀀽 = 350) and with larger Hamming weights (roughly 􀀽/10, and up to ℎ = 60 for 􀀽 = 350) . We achieve this dramatic improvement via a novel preprocessing step, which allows us to generate training data from a linear number of eavesdropped LWE samples (4􀀽) and changes the distribution of the data to improve transformer training. We also improve the secret recovery methods of Salsa and introduce a novel cross-attention recovery mechanism allowing us to read oﬀ the secret directly from the trained models. While Picante does not threaten NIST’s proposed LWE standards, it demonstrates signiﬁcant improvement over Salsa and could scale further, highlighting the need for future investigation into machine learning attacks on LWE with sparse binary secrets. 1 INTRODUCTION The race for post-quantum cryptography (PQC) is well underway. A large-scale quantum computer could solve the hard math problems underpinning most deployed public-key cryptographic systems, like RSA [40], in polynomial time. Small-scale quantum computers have already been built. Consequently, new post-quantum cryptographic systems were proposed and considered for standardization by US National Institute ofStandards and Technology(NIST) in the 5-year PQC competition. In July 2022, NIST standardized 4 schemes from the PQC competition [13] . The only key encapsulation mechanism selected—CRYSTALS-Kyber [6]—and one of the ∗ Co-ﬁrst authors. †Co-senior authors, corresponding author: [fcharton@meta.com](fcharton@meta.com) three signature schemes—CRYSTALS-Dilithium [25]—are based on the mathematical hardness assumption known as Learning With Errors (LWE) [39] . LWE is also used in proposed PQ homomorphic encryption schemes [2] . LWE works as follows: given an integer modulus􀁀, a dimension 􀀽, and a secret vector s ∈ Z􀀽􀁀, the Learning With Errors problem is to recover s given many random vectors and their noisy inner products with s. These noisy inner products are computed by taking random vector a ∈ Z􀀽􀁀 and producing 􀀱 := a · s + 􀀴 mod 􀁀, where 􀀴 is an “error” term sampled from a narrow discrete Gaussian distribution (i.e. taking small values). The adversary is then given the samples (a, 􀀱) and attempts to use these to recover s. The basic LWE problem is assumed to be hard for both classical and quantum adversaries [9, 31, 33, 38, 39] . Variants of LWE, like module-LWE or ring-LWE—on which the NIST-standards and HE schemes are based—add structure to the basic LWE problem, making them potentially easier than LWE. Classical attacks on LWE and its variants typically rely on algebraic techniques for lattice reduction to recover the secret s from pairs (a, 􀀱) [14, 30] . The error 􀀴 added to a · s to compute 􀀱 adds noise,

FAQs

What problem does LWE support in post-quantum cryptography?

LWE is a foundational hard mathematical problem used in multiple PQC systems, including mechanisms based on module LWE and homomorphic encryption schemes based on ring LWE.

What are the main limitations of the prior Salsa attack?

Salsa works only for small dimensions and very low Hamming weights, and it needs millions of eavesdropped LWE samples, making it difficult to scale to realistic attacker capabilities.

How does Picante improve upon Salsa for recovering sparse binary secrets?

Picante uses a novel preprocessing step to generate training data from a linear number of samples, improves transformer training through a changed data distribution, upgrades the recovery methods, and adds a cross-attention mechanism that reads the secret directly from trained models.

Aug 4, 2026

Upload by Logic