Date of Award
Hashing (Computer science), Image processing -- Digital techniques, Quantum complexity theory
This work proves an improved lower bound for the quantum query complexity of collision- finding in hash functions whose images are distributed according to a non-uniform distribution. Recent work by [TTU16] applied the leftover hash lemma to show that at least Omega(2k/9) quantum queries are necessary to find a collision when the image distribution has min-entropy k. In comparison, a result by [Zha15] implies that Omega(2k/3) quantum queries are necessary if the distribution is uniform. In this paper the lower bound complexity of [Zha15] is extended directly to the non-uniform case using a chain of reductions which convert collisions in min-entropy k distributions into collisions in the uniform distribution with constant probability. This result shows a minimum security guarantee for hash functions under more general assumptions in which the image distribution may not be uniform.
Balogh, Marko, "An Improved Lower Bound for the Quantum Query Complexity of Collision Finding in Hash Functions with Non-Uniformly Distributed Images" (2017). University Honors Theses. Paper 425.