期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
