CryptoDB
Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments
Authors: | |
---|---|
Download: | |
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.] |
BibTeX
@misc{eprint-1996-11271, title={Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments}, booktitle={IACR Eprint archive}, keywords={}, url={http://eprint.iacr.org/1996/004}, note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. ivan@daimi.aau.dk 10500 received May 14th, 1996.}, author={Ronald Cramer and Ivan Damgård}, year=1996 }