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.

In this work, we study transformations from private-coin proofs to public-coin proofs, which preserve (up to polynomial factors) the running time of both the prover and the verifier. 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. Can every private-coin doubly-efficient interactive proof be transformed into a public-coin doubly-efficient proof? We show that, assuming one-way functions exist, there is no black-box private-coin to public-coin transformation for doubly-efficient interactive proofs.

Our main result is a (loose) converse: every doubly-efficient proof has a function such that if this function is invertible, then the proof can be efficiently transformed.

Turning our attention back to classic interactive proofs, where the honest prover need not run in polynomial time, we show a similar result for constant-round general interactive proofs. Finally, we demonstrate a condition that suffices for efficiency preserving emulation of any protocol (even if the number of rounds is polynomial and the honest prover is unbounded). For a given interactive proof, if for every transcript prefix it is possible to efficiently approximate the number of consistent verifier random coins, then there is an efficiency-preserving transformation.

Minor refactoring

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.

Minor change to abstract

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 two such additional (incomparable) conditions. The first allows for transforming any {\em constant-round} interactive proof (even if it is not doubly-efficient). The second 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. 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.

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.

In this work, we study transformations from private-coin proofs to public-coin proofs, which preserve (up to polynomial factors) the running time of both the prover and the verifier. 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. Can every private-coin doubly-efficient interactive proof be transformed into a public-coin doubly-efficient proof? We show that, assuming one-way functions exist, there is no black-box private-coin to public-coin transformation for doubly-efficient interactive proofs.

Our main result is a (loose) converse: every doubly-efficient proof has a function such that if this function is invertible, then the proof can be efficiently transformed.

Turning our attention back to classic interactive proofs, where the honest prover need not run in polynomial time, we show a similar result for constant-round general interactive proofs. Finally, we demonstrate a condition that suffices for efficiency preserving emulation of any protocol (even if the number of rounds is polynomial and the honest prover is unbounded). For a given interactive proof, if for every transcript prefix it is possible to efficiently approximate the number of consistent verifier random coins, then there is an efficiency-preserving transformation.

* Changed first author's email address
* Clarifications to section 1
* Clarifications to section 5

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.

In this work, we study transformations from private-coin proofs to public-coin proofs, which preserve (up to polynomial factors) the running time of both the prover and the verifier. 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. Can every private-coin doubly-efficient interactive proof be transformed into a public-coin doubly-efficient proof? We show that, assuming one-way functions exist, there is no black-box private-coin to public-coin transformation for doubly-efficient interactive proofs.

Our main result is a (loose) converse: every doubly-efficient proof has a function such that if this function is invertible, then the proof can be efficiently transformed.

Turning our attention back to classic interactive proofs, where the honest prover need not run in polynomial time, we show a similar result for constant-round general interactive proofs. Finally, we demonstrate a condition that suffices for efficiency preserving emulation of any protocol (even if the number of rounds is polynomial and the honest prover is unbounded). For a given interactive proof, if for every transcript prefix it is possible to efficiently approximate the number of consistent verifier random coins, then there is an efficiency-preserving transformation.