Yael Tauman Kalai, Microsoft Research

Abstract

In this talk, I will present new constructions of publicly verifiable non-interactive delegation schemes, under (polynomial) falsifiable assumptions over bilinear groups. These schemes are in the common reference string (CRS) model, where the CRS is long (polynomial in the running time of the computation).

The first scheme is based on a decisional assumption, and supports any deterministic polynomial time computation. It is obtained by converting the delegation scheme of Kalai, Raz and Rothblum (STOC 2014) into a publicly verifiable one by constructing a homomorphic encryption scheme with a weak zero-test, a paradigm suggested by Paneth and Rothblum (TCC 2017). The second scheme is based on a (constant size) search assumption, but only supports log-space uniform circuits of bounded depth. It is obtained by converting the interactive delegation scheme of Goldwasser, Kalai and Rothblum (J. ACM 2015) into a non-interactive one, by replacing the sum-check protocol with a publicly verifiable non-interactive one.

Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model), or under non-standard assumptions related to obfuscation or multilinear maps.

This is joint work with Omer Paneth and Lisa Yang.