Paper 2017/688

Quantum Collision-Finding in Non-Uniform Random Functions

Marko Balogh, Edward Eaton, and Fang Song

Abstract

We give a complete characterization of quantum attacks for finding a collision in a non- uniform random function whose outputs are drawn according to a distribution of min-entropy k. This can be viewed as showing generic security of hash functions under relaxed assumptions in contrast to the standard heuristic of assuming uniformly random outputs. It also has ap- plications in analyzing quantum security of the Fujisaki-Okamoto transformation [TU TCC16B]. In particular, our results close a gap in the lower bound left open in [TTU PQCrypto16]. Specifically, let $D$ be a min-entropy $k$ distribution on a set $Y$ of size $N$. Let $f: X\to Y$ be a function whose output $f(x)$ is drawn according to $D$ for each $x \in X$ independently. We show that $\Omega(2^{k/3})$ quantum queries are necessary to find a collision in $f$, improving the previous bound $\Omega(2^{k/9})$. In fact we show a stronger lower bound $2^{k/2}$ in some special case. For all cases, we also describe explicit quantum algorithms that find a collision with a number of queries matching the corresponding lower bounds.

Note: proofs largely updated for modularity; added discussion on preimage and second preimage resistance

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
collision resistancequantum securityhash functions
Contact author(s)
fsong @ pdx edu
History
2017-11-26: revised
2017-07-18: received
See all versions
Short URL
https://ia.cr/2017/688
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/688,
      author = {Marko Balogh and Edward Eaton and Fang Song},
      title = {Quantum Collision-Finding in Non-Uniform Random Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/688},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/688}},
      url = {https://eprint.iacr.org/2017/688}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.