Welcome to the resource topic for 2017/688
Title:
Quantum Collision-Finding in Non-Uniform Random Functions
Authors: Marko Balogh, Edward Eaton, 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.
ePrint: https://eprint.iacr.org/2017/688
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .