Fetching the paper…

Reading the bibliography…

A Note on the Quantum Collision and Set Equality Problems · Around

2013

A Note on the Quantum Collision and Set Equality Problems

Zhandry, Mark

Original
PDF
Post on X

Understand

The results showing a quantum query complexity of $\Theta(N^{1/3})$ for the collision problem do not apply to random functions.

The issues are two-fold.
First, the $\Omega(N^{1/3})$ lower bound only applies when the range is no larger than the domain, which precludes many of the cryptographically interesting applications.
Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions.

Built on

Random oracles are practical: A paradigm for designing efficient protocols
Mihir Bellare and Phillip Rogaway · 1993
Earlier work this paper cites.
Quantum Algorithm for the Collision Problem
Gilles Brassard, Peter Høyer, and Alain Tapp · 1997
Earlier work this paper cites.
Quantum walk algorithm for element distinctness
Andris Ambainis · 2003
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson and Yaoyun Shi · 2004
Earlier work this paper cites.

Similar

A polynomial quantum query lower bound for the set equality problem
Gatis Midrijanis · 2004
Cited alongside, same era.
Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range
Andris Ambainis · 2005
Cited alongside, same era.
Random oracles in a quantum world
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry · 2010
Cited alongside, same era.
The need for structure in quantum speedups
Original
Scott Aaronson and Andris Ambainis · 2011
Cited alongside, same era.

Then

Secure identity-based encryption in the quantum random oracle model
Mark Zhandry · 2012
Later among the works it cites.
How to construct quantum random functions
Mark Zhandry · 2012
Later among the works it cites.
Secure signatures and chosen ciphertext security in a quantum computing world
Dan Boneh and Mark Zhandry · 2013
Closest in time.
A quantum lower bound for distinguishing random functions from random permutations
Original
Henry Yuen · 2013
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…