Document Zbl 0964.94019 - zbMATH Open

Zero-knowledge proofs for finite field arithmetic, or: Can zero-knowledge be for free? (English) Zbl 0964.94019

Krawczyk, Hugo (ed.), Advances in cryptology - CRYPTO ’98. 18th annual international cryptology conference, Santa Barbara, CA, USA, August 23-27, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1462, 424-441 (1998).

Summary: 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 Shamir’s (Shen’s) 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 [see A. Shamir, J. Assoc. Comput. Math. 39, 869-877 (1992; Zbl 0799.68096), A. Shen, ibid. 39, 878-880 (1992; Zbl 0799.68098)].
For the entire collection see [Zbl 0895.00067].