Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-066 | 19th April 2016 18:13

On Emulating Interactive Proofs with Public Coins


Authors: Oded Goldreich, Maya Leshkowitz
Publication: 19th April 2016 18:13
Downloads: 1316


The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol.
Specifically, the possible messages are essentially clustered according to the probability that they are selected in the original protocol, and the emulation selects a message at random among those that belong to the heaviest cluster.

We consider the natural alternative in which, at each round, if the parties play honestly, then each message is selected with probability that approximately equals the probability that it is selected in the original protocol.
This is done by selecting a cluster with probability that is proportional to its weight,
and picking a message at random in this cluster.
The crux of this paper is showing that, essentially, no matter how the prover behaves,
it cannot increase the probability that a message is selected by more than a constant factor (as compared to the original protocol).
We also show that such a constant loss is inevitable.

ISSN 1433-8092 | Imprint