# 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, whichallows 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.

Published

1996-01-07

How to Cite

*BRICS Report Series*,

*3*(7). https://doi.org/10.7146/brics.v3i7.19970

Issue

Section

Articles

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.