Date of Award

2017

Document Type

Thesis

Department

Physics

First Advisor

Fang Song

Subjects

Hashing (Computer science), Image processing -- Digital techniques, Quantum complexity theory

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.

Comments

An undergraduate honors thesis submitted in partial fulfillment of the requirements for the degree of Bachelor of Science in University Honors and Physics.

Persistent Identifier

http://archives.pdx.edu/ds/psu/20427

Share

COinS