Can Statistical Zero Knowledge be made NonInteractive?
or
On the Relationship of SZK and NISZK
Oded Goldreich,
Amit
Sahai, and Salil Vadhan
Abstract
We extend the study of noninteractive statistical zeroknowledge proofs.
Our main focus is to compare the class NISZK of problems possessing such
noninteractive proofs to the class SZK of problems possessing interactive
statistical zeroknowledge proofs. Along these lines, we first show that
if statistical zero knowledge is nontrivial then so is noninteractive
statistical zero knowledge, where by nontrivial we mean that the class
includes problems which are not solvable in probabilistic polynomialtime.
(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
zeroknowledge proofs can be made noninteractive.
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.
Versions

Advances in Cryptology  CRYPTO `99, vol. 1666 of Lecture Notes
in Computer Science, pp. 467484, SpringerVerlag, 1999.

Electronic Colloquium on Computational Complexity TR99013. [postscript]
[compressed
postscript]
[ back to
Salil Vadhan's research interests ]