link

January 26, Tuesday
12:00 – 13:30

A Parallel Repetition Theorem for Any Cryptographic Protocol
Computer Science seminar
Lecturer : Iftach Haitner
Lecturer homepage : http://research.microsoft.com/en-us/um/people/iftach/
Affiliation : Microsoft Research New England
Location : 202/37
Host : Prof. Amos Beimel
Whether or not parallel repetition improves security, is a fundamental question in the study of protocols. While parallel repetition improves the security of 3-message protocols and of public-coin protocols, Bellare, Impagliazzo and Naor (FOCS '97) gave an example of a protocol for which parallel repetition does not improve the security at all. We show that by slightly modifying any protocol, in a way that preserves its other properties, we get a protocol for which parallel repetition does improve the security (to any degree) .

In the second part of the talk (if time permits), I will presents our recent results on basing cryptography on minimal hardness assumptions, where we give simpler and more efficient (in some cases tight) constructions of pseudorandom generators, statistically hiding commitments and universal one-way hash functions based on one-way functions.