International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Ronald Cramer
Ivan Damgård
Download:
URL: http://eprint.iacr.org/1996/004
Search ePrint
Search Google
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.<br> [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
}