Cryptology ePrint Archive: Report 2019/603

How to Delegate Computations Publicly

Yael Kalai and Omer Paneth and Lisa Yang

Abstract: We construct a delegation scheme for all polynomial time computations. Our scheme is publicly verifiable and completely non-interactive in the common reference string (CRS) model.

Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps. 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.

We obtain our result in two steps. First, we construct a scheme with a long CRS (polynomial in the running time of the computation) by following the blueprint of Paneth and Rothblum (TCC 2017). Then we bootstrap this scheme to obtain a short CRS. Our bootstrapping theorem exploits the fact that our scheme can securely delegate certain non-deterministic computations.

Category / Keywords:

Date: received 30 May 2019

Contact author: omerpa at gmail com,yaelism@gmail com,lisayang@mit edu

Available format(s): PDF | BibTeX Citation

Version: 20190602:113205 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]