论文标题
通过可重复使用的量子步行查找许多碰撞
Finding many Collisions via Reusable Quantum Walks
论文作者
论文摘要
给定带有域$ [2^n] $的随机函数$ f $，$ m \ geq n $ $ [2^m] $，$ f $的碰撞是一对具有相同图像的独特输入。碰撞发现是密码分析中无处不在的问题，并且使用经典和量子算法对其进行了很好的研究。实际上，该问题的量子查询复杂性众所周知是$θ（2^{m/3}）$，并且匹配算法以任何$ m $的值而闻名。当人们寻找多个碰撞对时，情况就会不同。在这里，对于$ 2^k $碰撞，Liu and Zhandry（EuroCrypt〜2019）显示了$θ（2^{（2k+m）/3}）$的查询下限。匹配算法是众所周知的，但仅在存在许多碰撞时仅用于$ m $的较小值。在本文中，我们改善了此问题的算法，尤其是扩展了满足下限的可允许参数的范围。我们的新方法依赖于链式量子步行算法，这可能具有独立的兴趣。它允许提取MNRS风格的量子步行的多个解决方案，而无需完全重新计算它：找到和输出解决方案后，当前状态被重复使用为另一个步行的初始状态。作为应用程序，我们改善了最短矢量问题（SVP）的量子筛分算法，复杂性为$ 2^{0.2563D + O（d）} $，而不是先前的$ 2^{0.2570d + o（d）} $。
Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m \geq n$, a collision of $f$ is a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be $Θ(2^{m/3})$, and matching algorithms are known for any value of $m$. The situation becomes different when one is looking for multiple collision pairs. Here, for $2^k$ collisions, a query lower bound of $Θ(2^{(2k+m)/3})$ was shown by Liu and Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for relatively small values of $m$, when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met. Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk. As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of $2^{0.2563d + o(d)}$ instead of the previous $2^{0.2570d + o(d)}$.
