Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP

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 2^−50.

Keywords -- Interactive proofs, arguments, proofs of knowledge, computational security,
efficient general primitives, multi-bit commitment, statistical zero-knowledge.