**
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 |