Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
复制标题
通过有界距离解码改进最短向量问题的经典和量子算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yixin Shen
中科院分区：
文献类型：
--
作者：
Divesh Aggarwal;Yanlin Chen;Rajendra Kumar;Yixin Shen
。格上最重要的计算问题是最短向量问题(SVP)。在这篇文章中，我们提出了新的算法，以改善可证明的经典/量子SVP算法的现状。我们给出了以下结果。在时间2 1中运行的高级副总裁。669n+o(N)次和20次。5n+o(N)空间。这比[CCL18]的具有相同空间复杂度的算法有所改进。我们的经典和量子算法的时间复杂性是使用与晶格接吻数有关的量的已知上界得到的，该上限为20。402n.我们猜想，对于大多数晶格，这个量是20(N)。假设是这种情况，我们的经典算法在时间2 1内运行。292n+o(N)，我们的量子算法运行时间为20。750n+o(N)，我们的量子算法在QRAM模型中的运行时间为20。667n+o(N)。
. The most important computational problem on lattices is the Shortest Vector Problem ( SVP ). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP . We present the following results. SVP that runs in time 2 1 . 669 n + o ( n ) time and 2 0 . 5 n + o ( n ) space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is 2 0 . 402 n . We conjecture that for most lattices this quantity is a 2 o ( n ) . Assuming that this is the case, our classical algorithm runs in time 2 1 . 292 n + o ( n ) , our quantum algorithm runs in time 2 0 . 750 n + o ( n ) and our quantum algorithm in QRAM model runs in time 2 0 . 667 n + o ( n ) .