# Quantum Collision-Resistance of Non-Uniformly Distributed Functions

Quantum Collision-Resistance of Non-Uniformly Distributed FunctionsE. E. Targhi, G. N. Tabia, and D. Unruh (PQCrypto 2016).  [publisher's version | eprint]

Abstract: 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^{k/9})$ 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. the Fujisaki-Okamoto transform).