Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel repetition theorems for interactive arguments
| Content Provider | CiteSeerX |
|---|---|
| Author | Chung, Kai-Min Liu, Feng-Hao |
| Abstract | Abstract. We study efficient parallel repetition theorems for several classes of interactive arguments and obtain the following results: 1. We show a tight parallel repetition theorem for public-coin interactive arguments by giving a tight analysis for a reduction algorithm of H˚astad et al. [HPPW08]. That is, n-fold parallel repetition decreases the soundness error from δ to δ n. The crux of our improvement is a new analysis that avoid using Raz’s Sampling Lemma, which is the key ingredient to the previous results. 2. We give a new security analysis to strengthen a parallel repetition theorem of H˚astad et al. for a more general class of arguments. We show that n-fold parallel repetition decreases the soundness error from δ to δ n/2, which is almost tight. In particular, we remove the dependency on the number of rounds in the bound, and as a consequence, extend the “concurrent ” repetition theorem of Wikström [Wik09] to this model. 3. We obtain a way to turn any interactive argument to one in the class above using fully homomorphic encryption schemes. This gives a way to amplify the soundness of any interactive argument without increasing the round complexity. 4. We give a simple and generic transformation which shows that tight direct product theorems imply almost-tight Chernoff-type theorems. This extends our results to Chernoff-type theorems, and gives an alternative proof to the Chernoff-type theorem of Impagliazzo et al. [IJK09] for weakly-verifiable puzzles. Keywords: parallel repetition, interactive argument, public-coin, Arthur-Merlin, direct product theorem |
| File Format | |
| Journal | Electronic Colloquium on Computational Complexity (ECCC |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Interactive Argument Parallel Repetition Theorem Chernoff-type Theorem Soundness Error N-fold Parallel Repetition Homomorphic Encryption Scheme Tight Parallel Repetition Theorem Parallel Repetition Several Class Following Result Previous Result New Security Analysis Generic Transformation Reduction Algorithm Direct Product Theorem Weakly-verifiable Puzzle New Analysis Concurrent Repetition Theorem Tight Analysis Public-coin Interactive Argument Efficient Parallel Repetition Theorem Alternative Proof Tight Direct Product Key Ingredient General Class Raz Sampling Lemma Round Complexity Imply Almost-tight Chernoff-type Theorem |
| Content Type | Text |
| Resource Type | Article |
