Consider an interactive proof system for some set $S$ that has randomness complexity $r(n)$ for instances of length $n$, and arbitrary round complexity. We show a public-coin interactive proof system for $S$ of round complexity $O(r(n)/\log n)$. That is, the resulting interactive proof system is of the public-coin type even if the original was not. Furthermore, the randomness complexity is preserved up to a constant factor, and the resulting interactive proof system has perfect completeness.
In addition, we consider a natural alternative to the known public-coin emulation of interactive proof systems proposed by Goldwasser and Sipser. In the known emulation, 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. In our alternative emulation, each cluster is selected with probability that is proportional to its weight, and a message is picked at random from this cluster. The crux of our work 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 in compared to the original protocol. We also show that such a constant loss is inevitable.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, March 2017.
Available: the thesis (in PDF file).
Back to Oded Goldreich's homepage.