One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs.
Rafail Ostrovsky
Abstract: In this paper we explore several connections among one-way functions, hard on average problems, and zero-knowledge proofs which play an important role in cryptography and complexity theory. In particular, we consider the following two questions: First, if hard on the average problem possesses a statistical zero-knowledge proof, does this imply the existence of a one-way function? Second, while we know that such proofs can be given only to languages in \Sigmap 2 Pip2, the power of the prover in order to convince the verifier that x \in L was known to be contained only in probabilistic PSPACE and only under a specific algebraic assumption. Hence, can a better upper-bound (i.e. below PSPACE) be shown? We answer both questions in the affirmative. Resolving the first question, we show that if any hard on the average language possesses a Statistical Zero-Knowledge proof, then one-way functions exist. Resolving the second question, we show that under a general cryptographic assumption, the prover need not be more powerful then a randomized NP machine.
comment: Appeared in Proceedings of 6th Annual Structure in Complexity Theory Conference (STRUCTURES-91) June 30 -- July 3, 1991, Chicago. pp. 51-59.
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |