Summary: The authors extend the study of noninteractive statistical zero-knowledge proofs. Their main focus is to compare the class \(\mathcal {NISZK}\) of problems possessing such noninteractive proofs to the class \(\mathcal {SZK}\) of problems possing interactive statistical zero-knowledge proofs. Along these lines, they first show that if statistical zero knowledge is nontrivial then so is noninteractive statistical zero knowledge, where by nontrivial is meant 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, they show that if \(\mathcal {NISZK}\) is closed under complement, then in fact \(\mathcal {SZK}= \mathcal {NISZK}\), i.e. all statistical zero-knowledge proofs can be made non-interactive.
The main tools in this analysis are two promise problems that are natural restrictions of promise problems known to be complete for \(\mathcal {SZK}\). They show that these restricted problems are in fact complete for \(\mathcal {NISZK}\) and use this relationship to derive their 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. They also consider a weak form of \(\mathcal {NISZK}\), 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 \(\mathcal {NISZK}\) actually equals \(\mathcal {NISZK}\).
[The full version of this paper has been submitted to the Electronic Colloquium on Computational Complexity http://www.eccc.uni-trier.de/eccc/].
For the entire collection see [Zbl 0921.00042].