Abstract
A central question in the study of interactive proofs is the relationship between privatecoin proofs, where the verifier is allowed to hide its randomness from the prover, and publiccoin 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 privatecoin proofs into publiccoin ones. However, their transformation incurs a superpolynomial blowup in the running time of the honest prover.
In this work, we study transformations from privatecoin proofs to publiccoin proofs that preserve (up to polynomial factors) the running time of the prover. We reconsider this question in light of the emergence of doublyefficient interactive proofs, where the honest prover is required to run in polynomial time and the verifier should run in nearlinear time. Can every privatecoin doublyefficient interactive proof be transformed into a publiccoin doublyefficient proof? Adapting a result of Vadhan [STOC 2000], we show that, assuming oneway functions exist, there is no generalpurpose blackbox privatecoin to publiccoin transformation for doublyefficient interactive proofs.
Our main result is a loose converse: if (auxiliaryinput infinitelyoften) oneway functions do not exist, then there exists a generalpurpose efficiencypreserving transformation. To prove this result, we show a general condition that suffices for transforming a doublyefficient private coin protocol: every such protocol induces an efficiently computable function, such that if this function is efficiently invertible (in the sense of oneway functions), then the proof can be efficiently transformed into a publiccoin proof system with a polynomialtime honest prover.
This result motivates a study of other general conditions that allow for efficiencypreserving 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 efficiently approximate the number of verifier coins consistent with a partial transcript. This allows for transforming any constantround interactive proof that has this property (even if it is not doublyefficient). We demonstrate the applicability of this final result by using it to transform a privatecoin protocol of Rothblum, Vadhan and Wigderson [STOC 2013], obtaining a doublyefficient publiccoin protocol for verifying that a given graph is close to bipartite in a setting for which such a protocol was not previously known.
BibTeX  Entry
@InProceedings{arnon_et_al:LIPIcs.ITC.2021.3,
author = {Arnon, Gal and Rothblum, Guy N.},
title = {{On ProverEfficient PublicCoin Emulation of Interactive Proofs}},
booktitle = {2nd Conference on InformationTheoretic Cryptography (ITC 2021)},
pages = {3:13:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771979},
ISSN = {18688969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14322},
URN = {urn:nbn:de:0030drops143226},
doi = {10.4230/LIPIcs.ITC.2021.3},
annote = {Keywords: Interactive Proofs, Computational complexity, Cryptography}
}
Keywords: 

Interactive Proofs, Computational complexity, Cryptography 
Collection: 

2nd Conference on InformationTheoretic Cryptography (ITC 2021) 
Issue Date: 

2021 
Date of publication: 

19.07.2021 