The Many Entropies of One-Way Functions

One-way functions are the most basic, unstructured form of cryptographic hardness. Yet in a sequence of celebrated results (mostly in the eighties and early nineties), one-way functions were shown to imply a rich collection of cryptographic schemes and protocols (such as digital signatures and secret-key encryption). At the basis of this beautiful mathematical structure, are a few constructions of basic primitives: pseudorandom generators [Hastad-Impagliazzo-Levin-Luby ‘91], universal one-way hash functions [Naor-Yung ‘89, Rompel ‘90], and more recently statistically hiding commitments and statistical zero-knowledge arguments [Haitner-Nguyen-Ong-Reingold-Vadhan ‘06 & ‘07]. In all three cases, turning raw hardness into a much more exploitable cryptographic object requires some very elaborate constructions and proofs.

In this talk we will try to hint on how one-way functions naturally contain a basic form of each of these objects. The talk will be influenced by a recent line of results, simplifying and improving all of these constructions. The crux of each new construction is defining the “right” notion of computational entropy and recovering this form of entropy from one-way functions.

Based on several works with (subsets of) Iftach Haitner, Thomas Holenstein, Salil Vadhan and Hoteck Wee.