Estimating Quantum Speedups for Lattice Sieves
Estimating Quantum Speedups for Lattice Sieves
复制标题
估计格子筛的量子加速
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
John M. Schanck
中科院分区：
文献类型：
--
作者：
Martin R. Albrecht;Vlad Gheorghiu;Eamonn W. Postlethwaite;John M. Schanck
格筛算法的量子变体通常用于评估基于格的密码构造的安全性。在这项工作中，我们提供了一个启发式的，非渐近的，分析成本的几个算法的近邻搜索高维领域。这些算法是格筛的关键组成部分。我们设计用于近邻搜索算法的量子电路，并提供根据各种成本指标在数值上优化算法参数的软件。使用该软件，我们估计成本的经典和量子近邻搜索的领域。对于我们分析的最高性能近邻搜索算法，我们发现在密码分析兴趣的维度上有一个小的量子加速。实现这种加速需要几个乐观的物理和算法假设。
Quantum variants of lattice sieve algorithms are routinely used to assess the security of lattice based cryptographic constructions. In this work we provide a heuristic, non-asymptotic, analysis of the cost of several algorithms for near neighbour search on high dimensional spheres. These algorithms are key components of lattice sieves. We design quantum circuits for near neighbour search algorithms and provide software that numerically optimises algorithm parameters according to various cost metrics. Using this software we estimate the cost of classical and quantum near neighbour search on spheres. For the most performant near neighbour search algorithm that we analyse we find a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions.