[BGG+90] Everything Provable is Provable in Zero-Knowledge

Authors: Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, Phillip Rogaway | Venue: CRYPTO 1988 | Source

Abstract

Assuming the existence of a secure probabilistic encryption scheme, we show that every language that admits an interactive proof admits a (computational) zero-knowledge interactive proof. This result extends the result of Goldreich, Micali and Wigderson, that, under the same assumption, all of \textit{NP} admits zero-knowledge interactive proofs. Assuming envelopes for bit commitment, we show that every language that admits an interactive proof admits a perfect zero-knowledge interactive proof.

BibTeX

Copy

@Inproceedings{C:BGGHKM88,
  author = {Michael {Ben-Or} and Oded Goldreich and Shafi Goldwasser and Johan H{\aa}stad and Joe Kilian and Silvio Micali and Phillip Rogaway},
  title = {Everything Provable is Provable in Zero-Knowledge},
  pages = {37--56},
  editor = {Shafi Goldwasser},
  booktitle = {Advances in Cryptology -- {CRYPTO}'88},
  volume = {403},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~21--25},
  publisher = {Springer, New York, USA},
  year = {1990},
  doi = {10.1007/0-387-34799-2_4},
}