One-Way Functions and Kolmogorov Complexity

Abstract

This thesis surveys the theory of one-way functions, presenting their formal mathematical definitions and exploring their applications such as pseudorandom generators and secure cryptographic schemes. It concludes with the proof of a recently discovered central result: one-way functions exist if and only if t-time bounded Kolmogorov complexity is mildly hard-on-average. This result characterizes the feasibility of one-way functions, and therefore the feasibility of their applications, through a well-studied computational problem.