Everything provable is provable in zero-knowledge. (English) Zbl 0718.68033
Advances in cryptology - Crypto ’88, Proc. Conf., Santa Barbara, CA/USA 1988, Lect. Not. Comput. Sci. 403, 37-56 (1990).
Summary: [For the entire collection see Zbl 0709.00023.]
Assuming the existence of a secure probabilistic encryptionscheme, we show that every language that admits an interactive proof admits a (computational) zero-knowledge interactive proof. This result extends the result of O. Goldreich, S. Micali and A. Wigderson [Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th FOCS, 174-187 (1986)] that, under the same assumption, all of 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.
Assuming the existence of a secure probabilistic encryptionscheme, we show that every language that admits an interactive proof admits a (computational) zero-knowledge interactive proof. This result extends the result of O. Goldreich, S. Micali and A. Wigderson [Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th FOCS, 174-187 (1986)] that, under the same assumption, all of 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.
MSC:
| 68P25 | Data encryption (aspects in computer science) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 94A60 | Cryptography |
