License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.3
URN: urn:nbn:de:0030-drops-143226
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14322/
Arnon, Gal ;
Rothblum, Guy N.
On Prover-Efficient Public-Coin Emulation of Interactive Proofs
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 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 into a public-coin proof system with a polynomial-time honest prover.
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 efficiently approximate the number of verifier coins consistent with a partial transcript. This allows for transforming any constant-round interactive proof that has 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.
BibTeX - Entry
@InProceedings{arnon_et_al:LIPIcs.ITC.2021.3,
author = {Arnon, Gal and Rothblum, Guy N.},
title = {{On Prover-Efficient Public-Coin Emulation of Interactive Proofs}},
booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-197-9},
ISSN = {1868-8969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14322},
URN = {urn:nbn:de:0030-drops-143226},
doi = {10.4230/LIPIcs.ITC.2021.3},
annote = {Keywords: Interactive Proofs, Computational complexity, Cryptography}
}
|
Keywords: |
|
Interactive Proofs, Computational complexity, Cryptography |
|
Collection: |
|
2nd Conference on Information-Theoretic Cryptography (ITC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
19.07.2021 |
