Portal de Periódicos da CAPES

Everything Provable is Provable in Zero-Knowledge

1990; Springer Science+Business Media; Linguagem: Inglês

10.1007/0-387-34799-2_4

1611-3349

Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan H̊astad, Joe Kilian, Silvio Micali, Phillip Rogaway,

Complexity and Algorithms in Graphs

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 NP admits zero-knowledge interactive proofs. Assuming envelopes for bit commitment, we show tht every language that admits an interactive proof admits a perfect zero-knowledge interactive proof.