Welcome to the resource topic for
**1996/004**

**Title:**

Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments

**Authors:**
Ronald Cramer, 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.]

**ePrint:**
https://eprint.iacr.org/1996/004

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .