How to Delegate Computations Publicly

Yael Kalai; Omer Paneth; Lisa Yang

Paper 2019/603

How to Delegate Computations Publicly

Yael Kalai, 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): omerpa @ gmail com
yaelism @ gmail com
lisayang @ mit edu
History: 2019-06-02: received
Short URL: https://ia.cr/2019/603
License: CC BY

BibTeX

@misc{cryptoeprint:2019/603,
      author = {Yael Kalai and Omer Paneth and Lisa Yang},
      title = {How to Delegate Computations Publicly},
      howpublished = {Cryptology ePrint Archive, Paper 2019/603},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/603}},
      url = {https://eprint.iacr.org/2019/603}
}