On Emulating Interactive Proofs with Public Coins

Webpage for a paper by Oded Goldreich and Maya Leshkowitz


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.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.