Abstract:
We study the behavior of interactive arguments under sequential iteration, in particular how this affects the error probability. This problem turns out to be more complex than one might expect from the fact that for interactive proofs, the error trivially decreases exponentially in the number of iterations.
In particular, we study the typical efficient case where the iterated protocol is based on a single instance of a computational problem. This is not a special case of independent iterations of an entire protocol, and real exponential decrease of the error cannot be expected, but nevertheless, for practical applications, one needs concrete relations between the complexity and error probability of the underlying problem and that of the iterated protocol. We show how this problem can be formalized and solved using the theory of proofs of knowledge.
We also prove that in
the non-uniform model of complexity the error probability of independent
iterations of an argument does indeed decrease exponentially - to our
knowledge this is the first result about a strictly exponentially small error
probability in a computational cryptographic security property. As an
illustration of our first result, we present a very efficient zero-knowledge
argument for circuit satisfiability, and thus for any NP problem, based on
any collision-intractable hash function. Our theory applies to show the
soundness of this protocol. Using an efficient hash function such as SHA-1,
the protocol can handle about 20000 binary gates per second at an error level
of 
Available as PostScript, PDF, DVI.