Title :
A complete promise problem for statistical zero-knowledge
Author :
Sahai, Amit ; Vadhan, Salil P.
Author_Institution :
Dept. of Comput. Sci., MIT, Cambridge, MA, USA
Abstract :
We present a complete promise problem for SZK, the class of languages possessing statistical zero-knowledge proofs (against an honest verifier). The problem is to decide whether two efficiently samplable distributions are either statistically close or far apart. This characterizes SZK with no reference to interaction or zero-knowledge. From this theorem and its proof we are able to establish several other results about SZK, knowledge complexity, and efficiently samplable distributions
Keywords :
computational complexity; theorem proving; complete promise problem; complexity classes; honest verifier; knowledge complexity; samplable distributions; statistical zero-knowledge; statistical zero-knowledge proofs; Computer science; Cryptography; Distributed computing; Mathematics; Polynomials; Protocols; Tires;
Conference_Titel :
Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
Conference_Location :
Miami Beach, FL
Print_ISBN :
0-8186-8197-7
DOI :
10.1109/SFCS.1997.646133