Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors

📄 arXiv: 2402.01082v1 📥 PDF

作者: Samuel Stevens, Emily Wenger, Cathy Li, Niklas Nolte, Eshika Saxena, François Charton, Kristin Lauter

分类: cs.CR, cs.LG

发布日期: 2024-02-02

备注: 8 pages (main text)

💡 一句话要点

提出三种方法以提升机器学习对LWE问题的攻击效率

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: 学习与错误 后量子密码学 机器学习攻击 模型预训练 角嵌入 稀疏秘密 同态加密

📋 核心要点

  1. 现有的机器学习攻击LWE问题的方法需要数百万个样本进行训练，且恢复秘密的时间较长，效率低下。
  2. 本文提出了改进的预处理、角嵌入和模型预训练三种方法，以提高机器学习攻击的效率和效果。
  3. 实验结果显示，预处理速度提升了25倍，模型样本效率提升了10倍，首次在维度n=1024上成功恢复稀疏二进制秘密。

📝 摘要（中文）

学习与错误（LWE）是一个复杂的数学问题，支撑着新近标准化的后量子密码学系统。以往的研究提出了基于机器学习的攻击方法，但需要大量样本和长时间训练。本文提出了三种关键方法：改进预处理、角嵌入和模型预训练，显著提高了攻击效率，预处理速度提升25倍，模型样本效率提升10倍。首次证明预训练可以降低LWE攻击的成本，并成功在维度n=1024的情况下恢复稀疏二进制秘密，为同态加密应用提供了新的可能性。

🔬 方法详解

问题定义：本文旨在解决现有机器学习攻击LWE问题的效率低下，尤其是在处理小而稀疏的秘密时，现有方法需要大量样本和长时间训练，限制了其实用性。

核心思路：通过引入改进的预处理、角嵌入和模型预训练，提升机器学习模型在LWE问题上的样本效率和处理速度，从而加速攻击过程。

技术框架：整体架构包括三个主要模块：首先是数据预处理阶段，利用改进的方法加速样本准备；其次是角嵌入模块，将数据映射到更有利于模型学习的空间；最后是模型预训练阶段，通过在大规模数据集上进行预训练，提升模型的泛化能力。

关键创新：本文的主要创新在于首次证明了预训练可以有效降低机器学习攻击LWE的成本，并且在维度n=1024上成功恢复稀疏二进制秘密，突破了以往方法的限制。

关键设计：在参数设置上，优化了预处理算法的复杂度，损失函数采用了适应性调整策略，网络结构则引入了深度学习中的先进技术，如卷积层和全连接层的结合，以提高模型的学习能力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，改进的预处理方法使得样本准备速度提升了25倍，模型的样本效率提升了10倍。这些结果表明，预训练不仅降低了LWE攻击的成本，还使得在维度n=1024的情况下成功恢复稀疏二进制秘密成为可能，展示了显著的性能提升。

🎯 应用场景

该研究的潜在应用领域包括后量子密码学的安全性评估和加密算法的设计。通过提高对LWE问题的攻击效率，可以帮助研究人员更好地理解和改进现有的加密系统，从而增强数据安全性和隐私保护。未来，随着量子计算的发展，该研究可能对密码学领域产生深远影响。

📄 摘要（原文）

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.