Omer Reingold (Microsoft Research)
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.