Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II
Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II
复制标题
密码学进展 - ASIACRYPT 2020 - 第 26 届密码学理论与应用与信息安全国际会议，韩国大田，2020 年 12 月 7-11 日，会议记录，第二部分
DOI：
10.1007/978-3-030-64834-3_20
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Albrecht M
中科院分区：
文献类型：
--
作者：
Albrecht M
格筛算法的量子变体通常用于评估基于格的密码构造的安全性。在这项工作中，我们提供了一个启发式的，非渐近的，分析成本的几个算法的近邻搜索高维领域。这些算法是格筛的关键组成部分。我们设计用于近邻搜索算法的量子电路，并提供根据各种成本指标在数值上优化算法参数的软件。使用该软件，我们估计成本的经典和量子近邻搜索的领域。对于我们分析的最高性能近邻搜索算法，我们发现在密码分析兴趣的维度上有一个小的量子加速。实现这种加速需要几个乐观的物理和算法假设。
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.