[Resource Topic] 2017/575: Quantum Collision-Resistance of Non-uniformly Distributed Functions: Upper and Lower Bounds

Welcome to the resource topic for 2017/575

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

Authors: Ehsan Ebrahimi, 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.

ePrint: https://eprint.iacr.org/2017/575

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .