Computational Entropy and Cryptographic Constructions

Abstract

In the field of cryptography, the primitive of a one-way function is a powerful tool that can be effectively wielded to construct such tools as pseudorandom generators \citep{HILL99}, commitment schemes \citep{VZ11}, and universal one-way hash functions \citep{HHRVW10}. When first discovered, these constructions were intricate, complicated, and seemingly unmotivated. Recent work has been done to formalize several new notions of computational entropy including next-block pseudoentropy and inaccessible entropy. These entropy formulations make cryptographic constructions from one-way functions more modular and better expose the similarities between pseudorandom generators, commitment schemes, and universal one-way hash functions. This thesis will primarily explore the constructions of pseudorandom generators (PRGs), but will also touch on commitment schemes and universal one-way hash functions. The focus on this thesis will be on understanding the definitions of computational entropy, which may mean that some of the specifics of the construction of \cite{VZ11}'s PRG from an arbitrary one-way function may be lacking. In an effort to be self-contained, this paper also devotes time to understanding the ``historical'' development of computational entropy and to explaining the necessary mathematical and statistical background.