YoVDO

On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs

Offered By: Paul G. Allen School via YouTube

Tags

Cryptography Courses Theoretical Computer Science Courses Zero-Knowledge Proofs Courses

Course Description

Overview

Explore a 27-minute conference talk from the 2021 ITC Conference that delves into the randomness complexity of interactive proofs and statistical zero-knowledge proofs. Discover methods for reducing the number of random bits required by verifiers in interactive proofs and their application to statistical zero-knowledge proofs. Learn about the concept of randomness sparsification through the introduction of IP-PRG, its unconditional existence in non-uniform settings, and its existence under hardness assumptions in uniform settings. Examine the application of IP-PRG to SZK, the introduction of semi-malicious verifiers, and the resulting tradeoff between verifier randomness complexity and prover communication or simulation complexity. Gain insights into the canonical proof system for SD and its complete randomness sparsification. The talk covers key topics including problem statement, naive approach, genetic approach, nonuniformity, and statistical zero knowledge.

Syllabus

Introduction
Problem Statement
Naive Approach
Genetic Approach
Nonuniformity
Statistical Zero Knowledge


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