Rafail Ostrovsky - Publications

The (True) Complexity of Statistical Zero Knowledge.

Mihir Bellare, Silvio Micali, and Rafail Ostrovsky


A statistical zero-knowledge proof (SZK proof) is one for which this approximate view cannot be distinguished from the true view even when given unbounded computational resources. Statistical zero-knowledge is indeed a strong privacy requirement. In this paper, we, under a complexity assumption, Present a simpler condition on a language L which guarantees that L has a SZK proof, and thus reduce the difficulty of designing SZK proofs in practice, and Use this to prove various properties of the class of languages that possess SZK proofs. In proving the second result above, we actually exhibit a general paradigm for proving that the class of languages possessing SZK proofs has a given property.

comment: Appeared In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) May 14-16, 1990, Baltimore, Maryland.

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List