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

Download

Share

COinS