*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
