Report on the Security of LWE: Improved Dual Lattice Attack
Report on the Security of LWE: Improved Dual Lattice Attack
复制标题
LWE安全报告：改进的双格攻击
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Yong Xu
中科院分区：
文献类型：
--
作者：
Peng Lu;Yong Xu
许多领先的后量子密钥交换和签名方案依赖于错误学习(LWE)和舍入学习(LWR)问题及其代数变体的猜想难度，包括NIST PQC过程中6个最终入围方案中的3个。针对这些问题最著名的密码分析技术是原始和对偶格攻击，其中对偶攻击通常被认为不太实用。在这份报告中，我们提出了对偶格攻击的几个算法改进，使其效率超过原始攻击。在改进的攻击中，我们枚举了更多的秘密坐标，并使用了基于FFT的改进的识别器。此外，我们在RAM模型中加入了对执行格子筛选的成本估计的改进，减少了随机乘积码译码的门计数和执行更少的内积计算。结合这些改进，大大降低了基于LWE/LWR的决赛选手Kyber、Saber和Dilithium的安全级别，使它们低于NIST定义的门槛。
Many of the leading post-quantum key exchange and signature schemes rely on the conjectured hardness of the Learning With Errors (LWE) and Learning With Rounding (LWR) problems and their algebraic variants, including 3 of the 6 finalists in NIST’s PQC process. The best known cryptanalysis techniques against these problems are primal and dual lattice attacks, where dual attacks are generally considered less practical. In this report, we present several algorithmic improvements to the dual lattice attack, which allow it to exceed the efficiency of primal attacks. In the improved attack, we enumerate over more coordinates of the secret and use an improved distinguisher based on FFT. In addition, we incorporate improvements to the estimates of the cost of performing a lattice sieve in the RAM model, reducing the gate-count of random product code decoding and performing less inner product calculations. Combining these improvements considerably reduces the security levels of Kyber, Saber and Dilithium, the LWE/LWR based finalists, bringing them below the thresholds defined by NIST.