loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
38th Annual Symposium on Foundations of Computer Science (FOCS '97)
A Complete Promise Problem for Statistical Zero-Knowledge
Miami Beach, FL
October 19-October 22
ISBN: 0-8186-8197-7
Amit Sahai, Massachusetts Institute of Technology
Salil Vadhan, Massachusetts Institute of Technology
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.
Citation:
Amit Sahai, Salil Vadhan, "A Complete Promise Problem for Statistical Zero-Knowledge," focs, pp.448, 38th Annual Symposium on Foundations of Computer Science (FOCS '97), 1997
Usage of this product signifies your acceptance of the Terms of Use.