Quantum Collision-Resistance of Non-Uniformly Distributed Functions

Ehsan Ebrahimi Targhi; Gelo Noel Tabia; Dominique Unruh

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2016/015

Quantum Collision-Resistance of Non-Uniformly Distributed Functions

Ehsan Ebrahimi Targhi, 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).

Metadata

Available format(s): PDF
Publication info: Preprint.
Keywords: Quantum Collision Non-uniform distribution Query complexity
Contact author(s): ehsan ebrahimi targhi @ ut ee
History: 2016-01-08: received
Short URL: https://ia.cr/2016/015
License: CC BY

BibTeX

@misc{cryptoeprint:2016/015,
      author = {Ehsan Ebrahimi Targhi and Gelo Noel Tabia and Dominique Unruh},
      title = {Quantum Collision-Resistance of Non-Uniformly Distributed Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/015},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/015}},
      url = {https://eprint.iacr.org/2016/015}
}