One-Way Functions Are Essential for Non-Trivial Zero-Knowledge

TitleOne-Way Functions Are Essential for Non-Trivial Zero-Knowledge
Publication TypeTechnical Report
Year of Publication1993
AuthorsOstrovsky, R., & Wigderson A.
Other Numbers861

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).

Bibliographic Notes

ICSI Technical Report TR-93-073

Abbreviated Authors

R. Ostrovsky and A. Wigderson

ICSI Publication Type

Technical Report