Colloquium and ACT Seminar - Omer Reingold/Microsoft Research Silicon Valley "The Many Entropies of One-Way Functions", ACES 2.402
Type of Talk: Colloquium and ACT Seminar
on: Omer Reingold/Microsoft Research Silicon Valley
, December 14, 2010 4:00 p.m.
Location: ACES 2.402
Talk Title: "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 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.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct