On Transformations of Interactive Proofs that Preserve the Prover's Complexity

Abstract

Goldwasser and Sipser [GS89] proved that every interactive proof system can be transformed into a public-coin one (a.k.a., an Arthur-Merlin game). Their transformation has the drawback that the computational complexity of the prover's strategy is not preserved. We show that this is inherent, by proving that the same must be true of any transformation which only uses the original prover and verifier strategies as "black boxes". Our negative result holds even if the original proof system is restricted to be honest-verifier perfect zero knowledge and the transformation can also use the simulator as a black box. We also examine a similar deficiency in a transformation of Fürer et al. [FGM+89] from interactive proofs to ones with perfect completeness. We argue that the increase in prover complexity incurred by their transformation is necessary, given that their construction is a black-box transformation which works regardless of the verifier's computational complexity.