Omer Reingold (Microsoft Research)

Oneway functions are the most basic, unstructured form of
cryptographic hardness. Yet in a sequence of celebrated results
(mostly in the eighties and early nineties), oneway functions were
shown to imply a rich collection of cryptographic schemes and
protocols (such as digital signatures and secretkey encryption). At
the basis of this beautiful mathematical structure, are a few
constructions of basic primitives: pseudorandom generators
[HastadImpagliazzoLevinLuby '91], universal oneway hash functions
[NaorYung '89, Rompel '90], and more recently statistically hiding
commitments and statistical zeroknowledge arguments
[HaitnerNguyenOngReingoldVadhan '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 oneway 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 oneway functions. Based on several works with (subsets of) Iftach Haitner, Thomas Holenstein, Salil Vadhan and Hoteck Wee. 