Linear Zero-Knowledge: A Note on Efficient Zero-Knowledge Proofs and Arguments
Ronald Cramer and Ivan Damgård
We present a 4-move zero-knowledge proof system [21] 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)+O(k)$ bit commitments, where $c$ is a constant depending only on $L$. 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)\cdot max(k, l)$ bits, where $l$ is the security parameter for the prover. The protocols can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring. 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: our protocols allows proving/arguing satisfiability of a Boolean formula $\Phi$ (containing and-, or- and not-operators) with communication complexity at most $6n + 2$ commitments for the interactive proof and at most $5nl + 10l$ bits for the argument (assuming $k \leq l$), where $n$ is the number of times $\Phi$ reads an input variable. Thus, if we use $k = n$, the number of commitments required for the proof is linear in $n$. Finally, we present an application of our results that results in a protocol for oblivious transfer requiring $O(1)$ commitments of size $O(k)$ bits for a maximal cheating probability of $2^{-k}$. Corresponding results for multiparty computations follow from this.
BibTeX Citation
@inproceedings{CraDam97,
author = {Ronald Cramer and Ivan Damgård},
title = {Linear Zero-Knowledge: A Note on Efficient Zero-Knowledge Proofs and Arguments},
booktitle = {Proc.~29th ACM Symposium on Theory of Computing --- STOC~'97},
pages = {436--445},
year = {1997},
month = {5},
publisher = {ACM},
}