One-Way Functions Are Essential for Non-Trivial Zero-Knowledge
Title | One-Way Functions Are Essential for Non-Trivial Zero-Knowledge |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Ostrovsky, R., & Wigderson A. |
Other Numbers | 861 |
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). |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-073.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-073 |
Abbreviated Authors | R. Ostrovsky and A. Wigderson |
ICSI Publication Type | Technical Report |