TR99-013 Authors: Oded Goldreich, Amit Sahai, Salil Vadhan

Publication: 31st May 1999 11:31

Downloads: 1637

Keywords:

We extend the study of non-interactive statistical zero-knowledge

proofs. Our main focus is to compare the class NISZK of problems

possessing such non-interactive proofs to the class SZK of problems

possessing interactive statistical zero-knowledge proofs. Along these

lines, we first show that if statistical zero knowledge is non-trivial

then so is non-interactive statistical zero knowledge, where by

non-trivial we mean that the class includes problems which are not

solvable in probabilistic polynomial-time. (The hypothesis holds

under various assumptions, such as the intractability of the Discrete

Logarithm Problem.) Furthermore, we show that if NISZK is closed

under complement, then in fact SZK=NISZK, i.e. all statistical

zero-knowledge proofs can be made non-interactive.

The main tools in our analysis are two promise problems that are

natural restrictions of promise problems known to be complete for SZK.

We show that these restricted problems are in fact complete for NISZK

and use this relationship to derive our results comparing the two

classes. The two problems refer to the statistical difference, and

difference in entropy, respectively, of a given distribution from the

uniform one. We also consider a weak form of NISZK, in which only

requires that for every inverse polynomial 1/p(n), there exists a

simulator which achieves simulator deviation 1/p(n), and show that

this weak form of NISZK actually equals NISZK.