# Zero-Knowledge for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?

## Ronald Cramer and Ivan Damg{å}rd

```
```We present a general method for constructing commitment schemes
based on existence of $q$-one way group homomorphisms, in which elements in a
finite prime field $GF(q)$ can be committed to. A receiver of commitments can
non-interactively check whether committed values satisfy linear equations.
Multiplicative relations can be verified interactively with exponentially
small error, while communicating only a constant number of commitments.
Particular assumptions sufficient for our commitment schemes include: the RSA
assumption, hardness of discrete log in a prime order group, and polynomial
security of Diffie-Hellman encryption.
Based on these commitments, we give efficient zero-knowledge proofs and
arguments for arithmetic circuits over finite prime fields, namely given such
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 $m$-bit prime, a circuit of
size $O(m)$, and error probability $2^{-m}$, our protocols require
communication of $O(m^2)$ bits. We then look at the Boolean Circuit
Satisfiability problem and give non-interactive zero-knowledge proofs and
arguments with preprocessing. In the proof stage, the prover can prove any
circuit of size $n$ he wants by sending only one message of size $O(n)$ bits.
As a final 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.