The Many Entropies of One-Way Functions


November 17, 2010


Omer Reingold


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.


Omer Reingold

Omer Reingold is a Principal Researcher at Microsoft Research Silicon Valley and a Computer Science Professor at the Weizmann Institute of Science. His research is in the Foundations of Computer Science, mainly in Computational Complexity and Foundations of Cryptography. He received the 2005 Grace Murray Hopper Award and co-won the 2009 Gödel Prize.