Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving
Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving
复制标题
近似 k-列表问题的量子算法及其在格子筛分中的应用
DOI：
10.1007/978-3-030-34578-5_19
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Subhayan Roy Moulik
中科院分区：
文献类型：
--
作者：
E. Kirshanova;Erik Mårtensson;Eamonn W. Postlethwaite;Subhayan Roy Moulik
最短的向量问题（SVP）是基于晶格的加密基础的数学基础之一。晶格筛子算法是解决SVP的最重要方法之一。在\（2^{\ mathsf {c} d + o（d）} \）中使用\（2^{c {c {c {c} {c}'常数\（c，c'\）的D + O（d）} \）内存。在这项工作中，我们给出了各种量子筛分算法，以将计算步骤用于内存。
The Shortest Vector Problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a d-dimensional lattice in \(2^{\mathsf {c}d + o(d)}\) time steps with \(2^{\mathsf {c}' d + o(d)}\) memory for constants \(c, c'\). In this work, we give various quantum sieving algorithms that trade computational steps for memory.