Paper 2016/015

Quantum Collision-Resistance of Non-Uniformly Distributed Functions

Ehsan Ebrahimi Targhi and Gelo Noel Tabia and Dominique Unruh

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 $\Omega(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. Fujisaki-Okamoto transform).