Can Statistical Zero Knowledge be made Non-Interactive?
or
On the Relationship of SZK and NISZK
Oded Goldreich,
Amit
Sahai, and Salil Vadhan
Abstract
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.
Versions
-
Advances in Cryptology - CRYPTO `99, vol. 1666 of Lecture Notes
in Computer Science, pp. 467-484, Springer-Verlag, 1999.
-
Electronic Colloquium on Computational Complexity TR99-013. [postscript]
[compressed
postscript]
[ back to
Salil Vadhan's research interests ]