Cryptology ePrint Archive: Report 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).

Category / Keywords: Quantum, Collision, Non-uniform distribution, Query complexity

Date: received 7 Jan 2016

Contact author: ehsan ebrahimi targhi at ut ee

Available format(s): PDF | BibTeX Citation

Version: 20160108:000158 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]