Quantum Collision-Resistance of Non-Uniformly Distributed Functions.
Ehsan Ebrahimi, Gelo Noel M. Tabia, Dominique Unruh · IACR Cryptology ePrint Archive · 2016
We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a distribution with min-entropy k. We prove that Ω(2) quantum queries are necessary to find a collision for function f . This is needed in some security proofs in the quantum random oracle model (e.g. Fujisaki-Okamoto transform).