Comparing entropies in statistical zero knowledge with applications to the structure of SZK

被引：48

作者：

Goldreich, O ^{[1
]}

Vadhan, S ^{[1
]}

机构：

[1] Weizmann Inst Sci, Dept Comp Sci, IL-76100 Rehovot, Israel

来源：

FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 1999年

关键词：

D O I：

10.1109/CCC.1999.766262

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pair 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 ED. Thus, we obtain an alternative proof of Okamoto's result by which HVSZK (i.e., honest-verifier statistical zero knowledge) equals public-coin HVSZK. The new proof is much simpler than the original one. The above also yields a trivial proof that HVSZK: is closed under complementation (since ED easily reduces to its complement). Among the new results obtained is an equivalence of a weak notion of statistical zero knowledge to the standard one.

引用

页码：54 / 73

页数：20

共 26 条

[1] STATISTICAL ZERO-KNOWLEDGE LANGUAGES CAN BE RECOGNIZED IN 2 ROUNDS [J].