A Complete Promise Problem for Statistical Zero-Knowledge

@inproceedings{citeulike:579926, 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. 1...}, author = {Sahai and Vadhan}, booktitle = {FOCS: {IEEE} Symposium on Foundations of Computer Science ({FOCS})}, citeulike-article-id = {579926}, keywords = {szk}, posted-at = {2006-04-07 22:44:31}, priority = {2}, title = {A Complete Promise Problem for Statistical Zero-Knowledge}, url = {http://citeseer.ist.psu.edu/sahai97complete.html}, year = {1997} }

TY - CONF ID - citeulike:579926 L3 - citeulike-article-id:579926 TI - A Complete Promise Problem for Statistical Zero-Knowledge T2 - FOCS: {IEEE} Symposium on Foundations of Computer Science ({FOCS}) N2 - 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. 1... KW - szk AU - Sahai AU - Vadhan PY - 1997/// UR - http://citeseer.ist.psu.edu/sahai97complete.html ER -