At ASIACRYPT 2018, a digital attack based on linear least squares was introduced for a variant of the learning with errors (LWE) problem which omits modular reduction known as the integer learning with errors problem (ILWE). In this paper, we present a theoretical and experimental study of the effectiveness of the attack when applied directly to small parameter ILWE instances found in popular digital signature schemes such as CRYSTALS-Dilithium which utilize rejection sampling. Unlike other studies which form ILWE instances based on additional information obtained from side-channel attacks, we take a more direct approach to the problem by constructing our ILWE instance from only the obtained signatures. We outline and introduce novel techniques in our simulation designs such as modular polynomial arithmetic via matrices in $\mathbb{R}$, as well as algorithms for handling large sample sizes efficiently. Our experimental results reinforce the proclaimed security of signature schemes based on ILWE. We additionally discuss the implications of our work and digital signatures as a whole in regards to real-world applications such as in Intelligent Transportation Systems (ITS).

翻译：在ASIACRYPT 2018会议上，针对省略模约简的学习错误问题变体——整数学习错误问题，提出了一种基于线性最小二乘的数字攻击方法。本文通过理论与实验研究，探讨了该攻击直接应用于实际数字签名方案（如采用拒绝采样技术的CRYSTALS-Dilithium）中小参数ILWE实例的有效性。与基于侧信道攻击获取附加信息构建ILWE实例的研究不同，我们采用更直接的方法，仅通过已获取的签名构建ILWE实例。我们在仿真设计中提出并引入了创新技术，包括通过$\mathbb{R}$域矩阵实现的模多项式运算，以及高效处理大规模样本的算法。实验结果强化了基于ILWE的签名方案所宣称的安全性。此外，我们结合智能交通系统等实际应用场景，讨论了本研究工作及数字签名技术整体所蕴含的意义。