On Transformations of Interactive Proofs that Preserve the Prover's Complexity
Salil Vadhan
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 Furer 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.
Versions
[ back to
Salil Vadhan's research interests ]