Information Security and Cryptography Research Group

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

Ronald Cramer and Ivan Damgård

Advances in Cryptology — CRYPTO '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1462, pp. 424–441, Aug 1998.

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.

BibTeX Citation

@inproceedings{CraDam98,
    author       = {Ronald Cramer and Ivan Damgård},
    title        = {Zero-Knowledge for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?},
    editor       = {Hugo Krawczyk},
    booktitle    = {Advances in Cryptology --- CRYPTO~'98},
    pages        = 424--441,
    series       = {Lecture Notes in Computer Science},
    volume       = 1462,
    year         = 1998,
    month        = 8,
    publisher    = {Springer-Verlag},
}

Files and Links