YoVDO

On Prover-Efficient Public-Coin Emulation of Interactive Proofs

Offered By: Paul G. Allen School via YouTube

Tags

Theoretical Computer Science Courses Cryptography Courses Interactive Proof Systems Courses

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 Theory
Stanford 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