Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
复制标题
使用量子搜索更快地解决晶格中的最短向量问题
DOI：
10.1007/978-3-642-38616-9_6
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. V. D. Pol
中科院分区：
文献类型：
--
作者：
Thijs Laarhoven;M. Mosca;J. V. D. Pol
通过将Grover的量子搜索算法应用于Micciancio和Voulgaris，Nguyen和Vidick，Wang等人的格型算法，以及Pujol和Stehle的方法，我们得到了求解最短向量问题的改进的渐近量子结果.利用量子计算机，我们可以证明在时间上找到一个最短的向量2^1.799n？+？o（n），改进了经典的时间复杂度2^2.465n？+？Pujol和Stehle的o（n）和2^2n？+？o（n），而我们期望在时间上找到一个最短的向量2^0.312n？+？o（n），改进了经典的时间复杂度2^0.384n+？这些量子复杂性对于基于最短向量问题的后量子密码系统的参数选择具有重要的指导意义。关键词：格;最短向量问题;筛分;量子算法;量子搜索
By applying Grover’s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehle, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 2^1.799n?+?o(n), improving upon the classical time complexity of 2^2.465n?+?o(n) of Pujol and Stehle and the 2^2n?+?o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 2^0.312n?+?o(n), improving upon the classical time complexity of 2^0.384n?+?o(n) of Wang et al. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. Keywords: lattices; shortest vector problem; sieving; quantum algorithms; quantum search