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

Ehsan Ebrahimi; Dominique Unruh

Paper 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 $Ω (2^{k / 9})$ to $Ω (2^{k / 5})$ where $k$ is the min-entropy of $D$ .

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

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Quantum Collision Non-uniform distribution Query complexity.
Contact author(s): Ehsan Ebrahimi Targhi @ ut ee
unruh @ ut ee
History: 2017-06-20: received
Short URL: https://ia.cr/2017/575
License: CC BY

BibTeX

@misc{cryptoeprint:2017/575,
      author = {Ehsan Ebrahimi and Dominique Unruh},
      title = {Quantum Collision-Resistance of Non-uniformly Distributed Functions: Upper and Lower  Bounds},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/575},
      year = {2017},
      url = {https://eprint.iacr.org/2017/575}
}