On Relationships between Statistical Zero-Knowledge Proofs

AbstractThis paper solves several fundamental open problems about statistical zero-knowledge interactive proofs (SZKIPs). The following two theorems are proven: •If language L has a statistical zero-knowledge interactive proof against an honest verifier, then L has a statistical zero-knowledge “public-coin” interactive proof against an honest verifier. (Theorem 1) •If L has a statistical zero-knowledge public-coin interactive proof against an honest verifier then “the complement of L” has a statistical zero-knowledge constant (one) round interactive proof against an honest verifier. (Theorem 2) The following corollaries are obtained directly from these two theorems and the recent result by Goldreich, Sahai, and Vadhan (1998, “Proc. of STOC,” pp. 409–418). •[Public-coin SZKIP=Private-coin SZKIP].[Honest verifier SZKIP=Any verifier SZKIP]. If L has a statistical zero-knowledge interactive proof against an “honest verifier,” then L has a statistical zero-knowledge public-coin interactive proof against “any verifier.” •[SZKIP=co-SZKIP]. If L has a statistical zero-knowledge interactive proof, then the “complement” of L has a statistical zero-knowledge (public-coin) interactive proof. •[Bounded round SZKIP=Unbounded round SZKIP]. If L has a statistical zero-knowledge interactive proof, then L has a statistical zero-knowledge “constant (one) round” interactive proof against an honest verifier. •[Black-box simulation SZKIP=Auxiliary-input SZKIP]. If L has a statistical “auxiliary-input” zero-knowledge interactive proof, then L has a statistical “black-box simulation” zero-knowledge interactive proof