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

Ronald Cramer; Ivan Damgaard

Paper 1996/004 Original: eprint.iacr.org/1996/004 ↗

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

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.<br> [The rest of the abstract was truncated and appears below -- the library.]

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 1996-05-14: last updated; 1996-05-14: published
Short URL: https://ia.cr/1996/004
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:1996/004,
      author = {Ronald Cramer and Ivan Damgaard},
      title = {Linear Zero-Knowledge - A note on Efficient Zero-Knowledge Proofs and Arguments},
      howpublished = {Cryptology {ePrint} Archive, Paper 1996/004},
      year = {1996},
      url = {https://eprint.iacr.org/1996/004}
}