Quantum Collision-Resistance of Non-uniformly Distributed Functions: Upper and Lower Bounds

Quantum Collision-Resistance of Non-uniformly Distributed Functions: Upper and Lower Bounds (QIC, 2018)
Ehsan Ebrahimi Targhi, Dominique Unruh
[ eprint | official ]

We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a non-uniform distribution D. We derive some upper bounds and lower bounds depending on the min-entropy and the collision-entropy of D. In particular, we improve the previous lower bound in [CITE collision] from Ω(2^{k/9}) to Ω(2^{k/5}) where k is the min-entropy of D.