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

DSpace/Manakin Repository

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

Citable link to this page

. . . . . .

Title: On Transformations of Interactive Proofs that Preserve the Prover's Complexity
Author: Vadhan, Salil P.
Citation: Vadhan, 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.
Full Text & Related Files:
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.
Published Version: http://dx.doi.org/10.1145/335305.335330
Other Sources: http://reference.kfupm.edu.sa/content/o/n/on_transformation_of_interactive_proofs__1226297.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728403

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7588]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters