Show simple item record

dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2011-02-18T19:53:37Z
dc.date.issued2000
dc.identifier.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.en_US
dc.identifier.isbn1581131844en_US
dc.identifier.issn0737-8017en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4728403
dc.description.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 <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_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherAssociation for Computing Machineryen_US
dc.relation.isversionofhttp://dx.doi.org/10.1145/335305.335330en_US
dc.relation.hasversionhttp://reference.kfupm.edu.sa/content/o/n/on_transformation_of_interactive_proofs__1226297.pdfen_US
dash.licenseLAA
dc.subjectinteractive proof systemsen_US
dc.subjectArhtur-Merlin gamesen_US
dc.subjectzero-knowledge proofsen_US
dc.subjectpseudorandom permutationsen_US
dc.titleOn Transformations of Interactive Proofs that Preserve the Prover's Complexityen_US
dc.typeMonograph or Booken_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalProceedings of the Annual ACM Symposium on Theory of Computingen_US
dash.depositing.authorVadhan, Salil P.
dc.date.available2011-02-18T19:53:37Z
dc.identifier.doi10.1145/335305.335330*
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record