dc.contributor.author Vadhan, Salil P. dc.date.accessioned 2011-02-18T19:53:37Z dc.date.issued 2000 dc.identifier.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. en_US dc.identifier.isbn 1581131844 en_US dc.identifier.issn 0737-8017 en_US dc.identifier.uri http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728403 dc.description.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. en_US 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. dc.description.sponsorship Engineering and Applied Sciences en_US dc.language.iso en_US en_US dc.publisher Association for Computing Machinery en_US dc.relation.isversionof http://dx.doi.org/10.1145/335305.335330 en_US dc.relation.hasversion http://reference.kfupm.edu.sa/content/o/n/on_transformation_of_interactive_proofs__1226297.pdf en_US dash.license LAA dc.subject interactive proof systems en_US dc.subject Arhtur-Merlin games en_US dc.subject zero-knowledge proofs en_US dc.subject pseudorandom permutations en_US dc.title On Transformations of Interactive Proofs that Preserve the Prover's Complexity en_US dc.type Monograph or Book en_US dc.description.version Accepted Manuscript en_US dc.relation.journal Proceedings of the Annual ACM Symposium on Theory of Computing en_US dash.depositing.author Vadhan, Salil P. dc.date.available 2011-02-18T19:53:37Z dc.identifier.doi 10.1145/335305.335330 * dash.contributor.affiliated Vadhan, Salil
﻿