On Prover-Efficient Public-Coin Emulation of Interactive Proofs
Offered By: Paul G. Allen School via YouTube
Course Description
Overview
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.
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
Related Courses
Automata TheoryStanford University via edX Intro to Theoretical Computer Science
Udacity Computing: Art, Magic, Science
ETH Zurich via edX 理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera