## On Emulating Interactive Proofs with Public Coins

#### Webpage for a paper by Oded Goldreich and Maya Leshkowitz

#### Abstract

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

- First version posted:
Apr'16.
- Revisions: none yet.

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