Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-176 | 12th December 2019 14:40

On Prover-Efficient Public-Coin Emulation of Interactive Proofs

RSS-Feed




Revision #1
Authors: Gal Arnon, Guy Rothblum
Accepted on: 12th December 2019 14:40
Downloads: 53
Keywords: 


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.

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.



Changes to previous version:

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


Paper:

TR19-176 | 4th December 2019 09:35

On Prover-Efficient Public-Coin Emulation of Interactive Proofs





TR19-176
Authors: Gal Arnon, Guy Rothblum
Publication: 5th December 2019 03:56
Downloads: 130
Keywords: 


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.

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.



ISSN 1433-8092 | Imprint