Abstract:
We present a zero-knowledge proof system for any NP language
L, which allows showing that 
with error probability less than
using communication corresponding to 
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 , the communication complexity is
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 ). 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 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 
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 
). Thus, if we use k=n, the number
of commitments required for the proof is linear in n.
Available as PostScript, PDF, DVI.