论文标题
量子增强双重攻击
Quantum Augmented Dual Attack
论文作者
论文摘要
我们使用带有量子随机访问（QRACM）的经典记忆（QRACM）提出了对学习的双晶格攻击的量子增强变体。将我们的结果应用于文献中的晶格参数，我们发现我们的算法比以前的算法优于先前的算法，假设单位成本访问QRACM。在技术层面上，我们展示了如何通过利用FFT的相对稀疏度并使用量子振幅估计来获得在给定阈值以上的快速傅立叶变换（FFT）系数时获得量子加速。在这种情况下，我们还讨论了量子傅立叶变换的适用性。此外，我们对猜测部分的经典和量子预期的复杂性进行了更严格的分析，该系数遵循离散的高斯（mod \（q \））。
We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM. On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).
