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

Abstract

We present a zero-knowledge proof system [19] for any NP language L, which
allows showing that x in L with error probability less than 2^−k using communication
corresponding to O(|x|^c) + k 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 x in L, the communication complexity is O(|x|^c) max(k; l)
bits, where l is the security parameter for the prover. 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 2^−k 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 Phi 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 k <= l). Thus, if we use k = n,
the number of commitments required for the proof is linear in n.
Both protocols are also proofs of knowledge of an NP-witness of membership in
the language involved.