Wednesday, March 17, 2010
11:00pm

5126 Upson Hall

Abstract:

In cryptography, the major tasks are constructing secure and efficient cryptographic primitives (e.g., one-way functions and encryption schemes) based on more basic primitives and/or hardness assumptions. Security/hardness amplification refers to the task of constructing a full-fledged secure primitive from a "weakly" secure one. (Parallel) repetition is a simple and efficient way to amplify security and is useful for many settings. There has been a long line of research studying whether parallel repetition amplifies security for various models, and at what rate is the security amplified. Such results are usually referred to as parallel repetition theorems.

In this talk, I will present our recent work on parallel repetition theorems (and "Chernoff-type theorems") for a large class of interactive arguments and variants of "puzzle systems." These models capture the security properties of many primitives/protocols such as public-coin protocols, CAPTCHAs, MACs, commitment schemes, etc. Our results improve upon all previous known results on security amplification (some of them with more involved transformations than parallel repetition) and give tight bounds on the rate of security amplification in several settings.