DocumentCode :
3330250
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
fYear :
1997
fDate :
20-22 Oct 1997
Firstpage :
448
Lastpage :
457
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
Conference_Location :
Miami Beach, FL
ISSN :
0272-5428
Print_ISBN :
0-8186-8197-7
Type :
conf
DOI :
10.1109/SFCS.1997.646133
Filename :
646133
Link To Document :
بازگشت