On Prover-Efficient Public-Coin Emulation of Interactive Proofs

A central question in the study of interactive proofs is the connection between private-coin proofs, proofs where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where such hiding is not allowed.

In this work we inspect transformations from private-coin proofs to public-coin proofs that preserve the running time of the prover. We first show that if one-way functions exist, then there are no such transformations which are black-box even when restricted to work only on a small set of protocols. We then show properties which are sufficient for such transformations to be possible, specifically efficient distributional inversion and efficient approximate counting.

Based on joint work with Guy Rothblum.