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.
|
Year | DOI | Venue |
---|---|---|
2019 | 10.1145/3313276.3316411 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
bootstrapping, delegation, public verification | Conference | 2019 |
ISSN | ISBN | Citations |
0737-8017 | 978-1-4503-6705-9 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yael Tauman Kalai | 1 | 2502 | 104.65 |
Omer Paneth | 2 | 535 | 22.42 |
Lisa Yang | 3 | 0 | 3.04 |