Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

@article{citeulike:579925, abstract = {We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pairs of circuits, and yes instances (resp., no instances) are such pairs in which the first (resp., second) circuit generates a distribution with noticeably higher entropy. On one hand we show that any language having a (honest-verifier) statistical zero-knowledge proof is Karp-reducible to ED. On the other hand, we present a public-coin (honest-verifier) statistical zero-knowledge proof for...}, author = {Goldreich, Oded and Vadhan, Salil P. }, citeulike-article-id = {579925}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, keywords = {szk}, number = {063}, posted-at = {2006-04-07 22:44:06}, priority = {2}, title = {Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK}, url = {http://citeseer.ist.psu.edu/258539.html}, volume = {5}, year = {1998} }

TY - JOUR ID - citeulike:579925 L3 - citeulike-article-id:579925 TI - Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK JF - Electronic Colloquium on Computational Complexity (ECCC) VL - 5 IS - 063 N2 - We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pairs of circuits, and yes instances (resp., no instances) are such pairs in which the first (resp., second) circuit generates a distribution with noticeably higher entropy. On one hand we show that any language having a (honest-verifier) statistical zero-knowledge proof is Karp-reducible to ED. On the other hand, we present a public-coin (honest-verifier) statistical zero-knowledge proof for... KW - szk AU - Goldreich, Oded AU - Vadhan, Salil PY - 1998/// UR - http://citeseer.ist.psu.edu/258539.html ER -