I guess I missed this work, when it was first posted, but I was reminded of it during a discussion in my introduction to complexity reading group. Some student asked about the applicability of the transformation of private-coin interactive proofs into public-coin ones in the context of doubly-efficient interactive proofs, and Hila Dahari answered citing the result outlined below. I believe that this incident provides sufficient justification to include this work among my choices.
As indicated in the abstract, this result builds on Vadhan's work, which presented an analogous negative result in the context of general interactive proofs (which are not necessarily doubly-efficient). The proof system used by Vadhan to demonstrate the infeasibility of a transformation refers to a set that is not in BPP and uses a prover strategy that cannot be implement in polynomial-time. The current work augments this set so to allow for a polynomial-time prover strategy, and this augmentation complicates the entire argument.
A central question in the study of interactive proofs is the relationship between private-coin proofs, where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where the verifier's random coins are sent to the prover. The seminal work of Goldwasser and Sipser [STOC 1986] showed how to transform private-coin proofs into public-coin ones. However, their transformation incurs a super-polynomial blowup in the running time of the honest prover.
In this work, we study transformations from private-coin proofs to public-coin proofs that preserve (up to polynomial factors) the running time of the prover. We re-consider this question in light of the emergence of doubly-efficient interactive proofs, where the honest prover is required to run in polynomial time and the verifier should run in near-linear time. Can every private-coin doubly-efficient interactive proof be transformed into a public-coin doubly-efficient proof? Adapting a result of Vadhan [STOC 2000], we show that, assuming one-way functions exist, there is no general-purpose black-box private-coin to public-coin transformation for doubly-efficient interactive proofs.
Our main result is a loose converse: if (auxiliary-input infinitely-often) one-way functions do {\em not} exist, then there exists a general-purpose efficiency-preserving transformation. To prove this result, we show a general condition that suffices for transforming a doubly-efficient private coin protocol: every such protocol induces an efficiently computable function, such that if this function is efficiently invertible (in the sense of one-way functions), then the proof can be efficiently transformed.
This result motivates a study of other general conditions that allow for efficiency-preserving private to public coin transformations. We identify an additional (incomparable) condition to that used in our main result. This condition allows for transforming any private coin interactive proof where (roughly) it is possible to approximate the number of verifier coins consistent with a partial transcript. This allows for transforming any {\em constant-round} interactive proof that have this property (even if it is not doubly-efficient). We demonstrate the applicability of this final result by using it to transform a private-coin protocol of Rothblum, Vadhan and Wigderson [STOC 2013], obtaining a doubly-efficient public-coin protocol for verifying that a given graph is close to bipartite in a setting for which such a protocol was not previously known.
Available from ECCC TR19-176