Revision #1 Authors: Gal Arnon, Guy Rothblum

Accepted on: 12th December 2019 14:40

Downloads: 35

Keywords:

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

TR19-176 Authors: Gal Arnon, Guy Rothblum

Publication: 5th December 2019 03:56

Downloads: 114

Keywords:

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.