Quantum Collision-Resistance of Non-Uniformly Distributed Functions

Ehsan Ebrahimi Targhi; Gelo Noel Tabia; Dominique Unruh

Paper 2016/015 Original: eprint.iacr.org/2016/015 ↗

Quantum Collision-Resistance of Non-Uniformly Distributed Functions

Ehsan Ebrahimi Targhi

Gelo Noel Tabia

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.
History: 2016-01-08: last updated; 2016-01-08: published
Short URL: https://ia.cr/2016/015
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2016/015}
}