On Transformations of Interactive Proofs that Preserve the Prover's Complexity
MetadataShow full item record
CitationVadhan, 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.
AbstractGoldwasser 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4728403
- FAS Scholarly Articles