We use the recording queries technique of Zhandry [ Zha19 ] to prove lower bounds in the exponentially small success probability regime, with applications to time-space tradeoffs. We first extend the recording technique to the case of non-uniform input distributions and we describe a new simple framework for using it. Then, as an application, we prove strong direct product theorems for K-Search under a natural product distribution not considered in previous works, and for finding K distinct collisions in a uniform random function ]  . Finally, we use the latter result to obtain the first quantum time-space tradeoff that is not based on a reduction to K-Search. Namely, we demonstrate that any T-query algorithm using S qubits of memory must satisfy a tradeoff of T^3 S \geq \Omega( N^4)for finding \Theta(N) collisions in a random function. We conjecture that this result can be improved to ] T^2 S \geq \Omega(N^3), and we show that it would imply a T^2 S \geq%DIFDELCMD < \tilde{\Omega}%%% (N^2) tradeoff for Element Distinctness ]  .
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. We further show that any improvement to our lower bound would imply a %DIFDELCMD < \tilde{\Omega}%%% breakthrough for a related question about the Element Distinctness problem. 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 .
R
use the recording queries technique of Zhandry
study the problem of finding K collision pairs in a random function f :
R
Zha19
N
R
to prove lower bounds in the exponentially small success probability regime, with applications to time-space tradeoffs. We first extend the recording technique to the case of non-uniform input distributions and we describe a new simple framework for using it. Then, as an application, we prove strong direct product theorems for K-Search under a natural product distribution not considered in previous works, and for finding K distinct collisions in a uniform random function
\rightarrow
A
N
A
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
D
Finally, we use the latter result to obtain the first quantum time-space tradeoff that is not based on a reduction to K-Search.
D
T-query
R
satisfy a tradeoff of
perform a number T of queries that satisfies the tradeoff
R
N^4)for finding \Theta(N) collisions in a random function. We conjecture that this result can be improved to
K^3 N). Classically, the same question has only been settled recently by Dinur
A
Eurocrypt'20
A
, who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener achieves the optimal time-space tradeoff of
R
\geq \Omega(N^3), and we show that it
= \Theta(K^2 N). Our result limits the extent to which quantum computing may decrease this tradeoff. We further show that any improvement to our lower bound
D
T^2 S \geq
R
(N^2) tradeoff for Element Distinctness
breakthrough for a related question about the Element Distinctness problem. Our method is based on a novel application of Zhandry's recording query technique
A
Crypto'19
A
for proving lower bounds in the exponentially small success probability regime