We present zero-knowledge proofs and arguments for arithmetic circuits overnite prime elds, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a eld GF (q), where q is an n-bit prime, a circuit of size O(n), and error probability 2 ?n , our protocols require communication of O(n 2 ) 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 (n 3 log n) bits. Variations of the technique behind these protocols lead to other interesting applications. We rst look at the Boolean Circuit Satis ability problem and give zeroknowledge proofs and arguments for a circuit of size n and error probability 2 ?n in which there is an interactive preprocessing phase requiring communication of O(n 2 ) 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 su cient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Di e-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.
The methods of Cramer et al. REF lead to arguments with communication complexity linear in the size of the circuit.
Zero-Knowledge Proofs for Finite Field Arithmetic, or: Can Zero-Knowledge be for Free?
IN PROC. CRYPTO
Mathematics Computer Science