用数据重复提升机器学习攻击密钥密度，突破原有稀疏限制
Improving ML Attacks on LWE with Data Repetition and Stepwise Regression
- 通过重复训练样本扩大数据集，增强模型对密集密钥的识别能力
- 在重复数据下，模型可成功恢复超过3个活跃比特的密钥（原上限）
- 提出分步回归法专门处理高维密钥中的关键比特，适合密码分析研究者
学习带错误（LWE）问题是格密码学中的难题。在二元秘密最简情况下，即为带误差的子集和问题。已有研究表明，针对二元、三元及小值秘密的机器学习攻击在稀疏秘密情形下有效，尤其在经BKZ预处理的数据上，可成功恢复“残酷区域”（Nolte等，2024）中最多3个活跃比特的秘密。本文发现，使用更大规模训练集并引入重复样本，可实现对更密集秘密的恢复。实证表明，模型尝试恢复秘密的成功率与数据集大小、重复次数之间存在幂律关系。我们提出一种分步回归技术，用于恢复秘密中的“冷却比特”，显著提升攻击效果。
原文摘要 · Abstract (English)
The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography. In the simplest case of binary secrets, it is the subset sum problem, with error. Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets, succeeding on fairly sparse secrets. The ML attacks recover secrets with up to 3 active bits in the "cruel region" (Nolte et al., 2024) on samples pre-processed with BKZ. We show that using larger training sets and repeated examples enables recovery of denser secrets. Empirically, we observe a power-law relationship between model-based attempts to recover the secrets, dataset size, and repeated examples. We introduce a stepwise regression technique to recover the "cool bits" of the secret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。