Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments

Ivan Damgård
Ronald Cramer

April 1996


We present a zero-knowledge proof system for any NP language L, which allows showing that tex2html_wrap_inline27 with error probability less than tex2html_wrap_inline29 using communication corresponding to tex2html_wrap_inline31 bit commitments, where c is a constant depending only on L. The proof can be based on any bit commitment scheme with a particular set of properties. We suggest an efficient implementation based on factoring.

We also present a 4-move perfect zero-knowledge interactive argument for any NP-language L. On input tex2html_wrap_inline27 , the communication complexity is tex2html_wrap_inline41 bits, where l is the security parameter for the prover (The meaning of l is that if the prover is unable to solve an instance of a hard problem of size l before the protocol is finished, he can cheat with probability at most tex2html_wrap_inline29 ). Again, the protocol can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring.

We present an application of our techniques to multiparty computations, allowing for example t committed oblivious transfers with error probability tex2html_wrap_inline29 to be done simultaneously using O(t+k) commitments. Results for general computations follow from this.

As a function of the security parameters, our protocols have the smallest known asymptotic communication complexity among general proofs or arguments for NP. Moreover, the constants involved are small enough for the protocols to be practical in a realistic situation: both protocols are based on a Boolean formula tex2html_wrap_inline57 containing and-, or- and not-operators which verifies an NP-witness of membership in L. Let n be the number of times this formula reads an input variable. Then the communication complexity of the protocols when using our concrete commitment schemes can be more precisely stated as at most 4n+k+1 commitments for the interactive proof and at most 5nl +5l bits for the argument (assuming tex2html_wrap_inline67 ). Thus, if we use k=n, the number of commitments required for the proof is linear in n.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.