Goldwasser and Sipser proved that a private coin interactive proof system can be converted into a public coin system. This conversion preserves round complexity (up to an additive factor of 2), but does not preserve prover complexity or zero-knowledge.

I am interested specifically in the ZK property. One could ask whether the non-preservation of ZK is a limitation of Goldwasser-Sipser or is inherent to this type of conversion.

I interpret a result of Goldreich and Krawczyk as indicating that non-preservation of ZK is inherent to such transformations if they are black-box. In particular, Goldreich and Krawczyk showed that there is no constant-round public-coin black-box zero-knowledge protocols for languages outside BPP.

My question has three parts:

(1) Am I correct to interpret the Goldreich and Krawczyk result as ruling out a private coin to public coin transformation that preserves ZK (in the black box setting)?

(2) What is the intuition for this? In particular, I don't see a clear reason why making the verifier's randomness public makes it harder for the prover to keep their information private.

(3) Are there any results for ZK-preserving non-black-box conversions?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.