Vadhan, Salil2011-02-182000Vadhan, Salil P. 2000. On transformations of interactive proofs that preserve the prover's complexity. In Proceedings of the thirty-second annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, Oregon (STOC 2000), 200-207. New York: ACM.15811318440737-8017http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728403Goldwasser 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 <i>et al.</i> [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.en-USinteractive proof systemsArhtur-Merlin gameszero-knowledge proofspseudorandom permutationsMonograph or Book2011-02-1810.1145/335305.335330