**
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 \Sigma^{p }_{2} Pi^{p}_{2}, 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 |