February 12, 2024
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 efficiency reasons. Prior work Salsa [51] demonstrated a machine learning based 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 off the secret directly from the trained models. While Picante does not threaten NISTā€™s proposed LWE standards, it demonstrates significant improvement over Salsa and could scale further, highlighting the need for future investigation into machine learning attacks on LWE with sparse binary secrets.
Written by
Cathy Li
Jana Sotakova
FranƧois Charton
Emily Wenger
Evrard Garcelon
Mohamed Mahlou
Publisher
Arxiv
Research Topics
Core Machine Learning
August 16, 2024
Zhihan Xiong, Maryam Fazel, Lin Xiao
August 16, 2024
August 12, 2024
Arman Zharmagambetov, Yuandong Tian, Aaron Ferber, Bistra Dilkina, Taoan Huang
August 12, 2024
August 09, 2024
Emily Wenger, Eshika Saxena, Mohamed Malhou, Ellie Thieu, Kristin Lauter
August 09, 2024
August 02, 2024
August 02, 2024
Foundational models
Latest news
Foundational models