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