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 |