Welcome to the resource topic for 1996/004
Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments
Authors: Ronald Cramer, Ivan DamgaardAbstract:
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.]
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 .