\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input x is in a language without revealing any additional information about x that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS 2000) allows a computationally-limited client to publish a single (randomized) message, E ( x ) , from which the server learns whether x is in and nothing else.

It is known that SRE, the class of problems that admit statistically private randomized encoding with polynomial-time client and computationally-unbounded server, is contained in the class SZK of problems that have statistical zero-knowledge proof. However, the exact relation between these two classes, and, in particular, the possibility of equivalence was left as an open problem.

In this paper, we explore the relationship between SRE and SZK, and derive the following results: (1) In a non-uniform setting, statistical randomized encoding with one-side privacy (1RE) is equivalent to non-interactive statistical zero-knowledge (NISZK). These variants were studied in the past as natural relaxation/strengthening of the original notions. Our theorem shows that proving SRE=SZK is equivalent to showing that 1RE=SRE and SZK=NISZK. The latter is a well-known open problem (Goldreich, Sahai, Vadhan, CRYPTO 1999).

(2) If SRE is non-trivial (not in BPP), then infinitely-often one-way functions exist. The analog hypothesis for SZK yields only \emph{auxiliary-input} one-way functions (Ostrovsky, Structure in Complexity Theory, 1991), which is believed to be a significantly weaker implication.

(3) If there exists an average-case hard language with \emph{perfect randomized encoding}, then collision-resistance hash functions (CRH) exist. Again, a similar assumption for SZK implies only constant-round statistically-hiding commitments, a primitive which seems weaker than CRH.

We believe that our results sharpen the relationship between SRE and SZK and illuminates the core differences between these two classes.