Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments
Ronald Cramer and Ivan Damgaard
Abstract:
We present a zero-knowledge proof system for any NP language L, which
allows showing that x is in L using communication corresponding
to $O(|x| sup c)+k$ bit commitments, with error probability $2 sup -k$,
and 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. The protocol allows showing
that a Boolean formula of size n is satisfiable,
with error probability $2 sup -n$, using O(n) commitments.
This is the first protocol for SAT that is linear in this sense.
[The rest of the abstract was truncated and appears below -- the library.]
Keywords: Interactive proofs, Zero-Knowledge, Secret Sharing
comment: received May 14th, 1996.
contact author: ivan@daimi.aau.dk
Fetch PostScript file of the full paper.
Rest of the Abstract:
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| sup c) max(k,l) bits, where l is the security parameter for the
prover, i.e. 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 2 sup -k.
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 sup -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 complexities of the
protocols when using our concrete commitment schemes are at most 4n+k+1
commitments for the interactive proof and at most 5nl +5l bits for the
argument (assuming k < l).