*********************************
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
*********************************
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.
