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 \Omega(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 = \Theta(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 \Omega(N^3)$ for sorting $N$ numbers on a quantum computer, which was first obtained by Klauck, \v{S}palek and de Wolf [K\v{S}W07].
翻译：我们研究了在量子计算机上使用随机函数$f：[N] \rightarrow [N]$寻找$K$个冲突对的问题。我们证明了，当可用内存的大小受限时，量子随机oracle模型中对函数的查询次数必须显著增加。即，我们证明了任何使用$S$比特内存的算法必须执行一定数量的查询$T$，满足权衡$ T ^ 3S \geq \Omega（K ^ 3N）$。经典上，同一个问题最近才被Dinur[Eurocrypt'20]解决，他表明了van Oorschot和Wiener的Parallel Collision Search算法实现了最优的时间 - 空间权衡$T ^ 2S = \Theta（K ^ 2N）$。我们的结果限制了量子计算可能降低此权衡的程度。我们的方法基于Zhandry的记录查询技术[Crypto'19]的新颖应用，用于证明指数小的成功概率范围内的下限。作为第二个应用，我们提供了一个简单的证明，证明了在量子计算机上对$ N $个数字进行排序的时间 - 空间权衡$ T ^ 2S \geq \Omega（N ^ 3）$，这是由Klauck，\v{S}palek和de Wolf率先获得的[K\v{S}W07]。
相关内容
微信扫码咨询专知VIP会员