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

Quantum Collision-Resistance of Non-uniformly Distributed Functions: Upper and Lower BoundsE. E. Targhi and D. Unruh (unpublished, 2017).  [eprint]

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 in Targhi, Tabia, Unruh, Quantum Collision-Resistance of Non-Uniformly Distributed Functions, 2016 from Ω(2^{k/9}) to Ω(2^{k/5}) where k is the min-entropy of D.

Permalink: