Cryptology ePrint Archive: Report 2017/575

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

Ehsan Ebrahimi 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 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 by Ebrahimi, Tabia, and Unruh from $\Omega(2^{k/9})$ to $\Omega(2^{k/5})$ where $k$ is the min-entropy of $D$.

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

Date: received 8 Jun 2017, last revised 15 Jun 2017

Contact author: Ehsan Ebrahimi Targhi at ut ee, unruh@ut ee

Available format(s): PDF | BibTeX Citation

Note: The \cite issue in abstract has addressed. We added email to of authors to the paper.

Version: 20170620:152335 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]