ECCC-Report TR19-176https://eccc.weizmann.ac.il/report/2019/176Comments and Revisions published for TR19-176en-usThu, 12 Dec 2019 14:40:25 +0200
Revision 1
| On Prover-Efficient Public-Coin Emulation of Interactive Proofs |
Gal Arnon,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2019/176#revision1A 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.Thu, 12 Dec 2019 14:40:25 +0200https://eccc.weizmann.ac.il/report/2019/176#revision1
Paper TR19-176
| On Prover-Efficient Public-Coin Emulation of Interactive Proofs |
Gal Arnon,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2019/176A 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.Thu, 05 Dec 2019 03:56:16 +0200https://eccc.weizmann.ac.il/report/2019/176