Colloquium and ACT Seminar - Omer Reingold/Microsoft Research Silicon Valley "The Many Entropies of One-Way Functions", ACES 2.402

Contact Name: 
Jenna Whitney
Dec 14, 2010 4:00pm - 5:00pm

Type of Talk: Colloquium and ACT Seminar


on: Omer Reingold/Microsoft Research Silicon Valley

Date/Time: Tuesday

, December 14, 2010 4:00 p.m.

Location: ACES 2.402

Host: David


Talk Title: "The Many Entropies of One-Way Functions"


alk Abstract:
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 si

gnatures and secret-key encryption). At the basis of this beautiful mathema

tical structure, are a few constructions of basic primitives: pseudorandom
generators [Hastad-Impagliazzo-Levin-Luby ''91], universal one-way hash f

unctions [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 hardnes

s into a much more exploitable cryptographic object requires some very elab

orate constructions and proofs.

In this talk we will try to hint on ho

w 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 f

orm of entropy from one-way functions.

Based on several works with (su

bsets of) Iftach Haitner, Thomas Holenstein, Salil Vadhan and Hoteck Wee.