Institute of Information Science, Academia Sinica

Events

Print

Press Ctrl+P to print from browser

Recent Progress on Parallel Repetition

:::

Recent Progress on Parallel Repetition

  • LecturerDr. Kai-Ming Chung (Dept. of CS, Cornell University)
    Host: Tsan-sheng Hsu
  • Time2012-03-28 (Wed.) 10:30 ~ 12:00
  • LocationAuditorium 106 at new IIS Building
Abstract

    

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

Taken together, these results resolve several questions left open in the seminal works of [Bellare, Goldreich, Goldwasser, FOCS’90], and [Bellare, Impagliazzo, Naor, FOCS’97].