Abstract:
We present zero-knowledge proofs and arguments for arithmetic
circuits over finite prime fields, namely given a circuit, show in
zero-knowledge that inputs can be selected leading to a given output. For a
field GF(q), where q is an n-bit prime, a circuit of size O(n), and
error probability 
, our protocols require communication of 
bits. This is the same worst-cast complexity as the trivial (non
zero-knowledge) interactive proof where the prover just reveals the input
values. If the circuit involves n multiplications, the best previously
known methods would in general require communication of 
bits.
Variations of the technique behind these protocols lead to other
interesting applications. We first look at the Boolean Circuit Satisfiability
problem and give zero-knowledge proofs and arguments for a circuit of size
n and error probability in which there is an interactive
preprocessing phase requiring communication of bits. In this phase,
the statement to be proved later need not be known. Later the prover can
non-interactively prove any circuit he wants, i.e. by sending only one
message, of size O(n) bits.
As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proof system with the same asymptotic communication complexity and number of rounds.
The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Diffie-Hellman encryption.
We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters
Available as PostScript, PDF, DVI.