论文标题
寻找多个碰撞对的量子时间空间折衷
Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
论文作者
论文摘要
我们研究了在随机函数中找到$ K $碰撞对的问题$ f：[n] \ rightarrow [n] $通过使用量子计算机。我们证明，当可用内存的大小受到限制时，量子随机甲骨文模型中对函数的查询数必须显着增加。也就是说，我们证明了使用$ s $ QUBITS内存的任何算法都必须执行满足折衷的$ t $查询的数字$ t $ t^3 s \ geqω（k^3 n）$。从经典上讲，同样的问题是最近才由Dinur [Eurocrypt'20]解决的，后者表明van Oorschot和Wiener的平行碰撞搜索算法实现了$ t^2 s =θ（k^2 n）$的最佳时空交易。我们的结果限制了量子计算可以减少此权衡的程度。我们的方法基于Zhandry的记录查询技术[Crypto'19]的新应用，以证明在指数级的成功概率方面的下限。作为第二个应用程序，我们为在量子计算机上排序$ n $数字的时空权衡$ t^2 s \ geqω（n^3）$提供了更简单的证明，这是由克拉克，špalek和de Wolf [kšw07]首次获得的。
We study the problem of finding $K$ collision pairs in a random function $f : [N] \rightarrow [N]$ by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using $S$ qubits of memory must perform a number $T$ of queries that satisfies the tradeoff $T^3 S \geq Ω(K^3 N)$. Classically, the same question has only been settled recently by Dinur [Eurocrypt'20], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener achieves the optimal time-space tradeoff of $T^2 S = Θ(K^2 N)$. Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry's recording query technique [Crypto'19] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time-space tradeoff $T^2 S \geq Ω(N^3)$ for sorting $N$ numbers on a quantum computer, which was first obtained by Klauck, Špalek and de Wolf [KŠW07].
