Date of Award
5-26-2017
Document Type
Thesis
Degree Name
Bachelor of Science (B.S.) in Physics and University Honors
Department
Physics
First Advisor
Fang Song
Subjects
Quantum theory, Hashing (Computer science), Collisions (Nuclear physics)
DOI
10.15760/honors.421
Abstract
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.
Persistent Identifier
http://archives.pdx.edu/ds/psu/20427
Recommended Citation
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.
https://pdxscholar.library.pdx.edu/honorstheses/425
10.15760/honors.421