Parallel Repetition Theorems for Interactive Arguments

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

1

We give a new security analysis to strengthen a parallel repetition theorem of Håstad 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.

1

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.

1

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.