Rafail Ostrovsky - Publications

One-Way Functions are Essential for Non-Trivial Zero-Knowledge.

Rafail Ostrovsky, Avi Wigderson

Abstract: It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. We prove that unless very weak one-way functions exist, Zero-Knowledge proofs can be given only for languages in BPP. For average-case definitions of BPP we prove an analogous result under the assumption that uniform one-way functions do not exist.

Thus, very loosely speaking, zero--knowledge is either useless (exists only for ``easy'' languages), or universal (exists for every provable language).

comment: Appeared In Proceedings of the second Israel Symposium on Theory of Computing and Systems (ISTCS-93) Netanya, Israel, June 7th-9th, 1993. Received Henry H. Taub Prize and 1,000 Award.

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

Back to Publications List