Explore a conference talk from the 2021 ITC Conference that delves into the relationship between private-coin and public-coin interactive proofs. Learn about the challenges in transforming private-coin proofs into public-coin ones while preserving the prover's efficiency. Discover the main theorem presenting sufficient properties for efficient transformations and its implications for doubly-efficient interactive proofs. Examine the impact of one-way functions on these transformations and investigate general conditions allowing for efficiency-preserving conversions. Gain insights into an application of these findings to transform a private-coin protocol for verifying graph properties into a doubly-efficient public-coin protocol.
Overview
Syllabus
On Prover-Efficient Public-Coin Emulation of Interactive Proofs
Can We Transform Private-Coin Proofs To Public-Coin?
Main Theorem: Sufficient properties for efficient transformations
An application
Set Lower-Bound Protocol (Baba) Sets (0,1) with efficient membership test
Emulating General Interactive Proofs
Unknown Number of Equally Likely Messages
Set Lower-Bound Protocol For #Consistent Coins
In the general case: • Messages With Varying Likelihood
Taught by
Paul G. Allen School
