Theory Seminar

Recent Progress on Parallel Repetition

Kai-Min Chung

Cornell University
Monday, March 11, 2013
12:00pm - 1:30pm
BBB 3941

Add to Google Calendar
Feel free to bring your own lunch.

About the Event

Cryptographic protocols have been developed for a variety of tasks, including verifiable delegation of computation, electronic voting system, privacy preserving data mining and more. A central method for constructing such protocols is to first construct a "basic" protocol satisfying a weak level of security, and then amplify the security of the protocol by running multiple instances of the basic protocol in parallel; this is referred to as a "parallel repetition". In this talk we present several general *parallel repetition theorems*, identifying general classes of protocols for which such parallel repetition amplifies the security level, while at the same time determining the optimal number of parallel repetitions, and the amount of extra randomness needed, to perform such security amplification. In addition, we will briefly mention several applications of parallel repetition in cryptography.


Kai-Min Chung is a postdoc in the Computer Science Department at Cornell University, supported by Simons Postdoctoral Fellowship in 2010-2012. Before joining Cornell, he received his PhD in Computer Science from Harvard University in 2011, and his BSE from National Taiwan University in 2003. His research interests are in the fields of cryptography, complexity theory, and pseudo-randomness, with focuses on investigating the power of interaction and randomness.

Additional Information

Contact: Yaoyun Shi

Phone: 7348469432


Sponsor(s): Yaoyun Shi

Open to: Public