PCP and Delegating Computation: A Love Story.

PCP and Delegating Computation: A Love Story - Yael Tauman Kalai

Yael Tauman Kalai
Microsoft Research
January 28, 2019

In this talk, I will give an overview on how PCPs, combined with cryptographic tools,
are used to generate succinct and efficiently verifiable proofs for the correctness of computations.
I will focus on constructing (computationally sound) *succinct* proofs that are *non-interactive*
(assuming the existence of public parameters) and are *publicly verifiable*.
In particular, I will focus on a recent result with Omer Paneth and Lisa Yang,
where we show how to construct such proofs for all polynomial time computations,
based on an efficiently falsifiable decisional assumption on groups with bilinear maps.
Prior to this work, this was only known under non-standard assumptions.