Paper 2018/776

On Publicly Verifiable Delegation From Standard Assumptions

Yael Kalai, Omer Paneth, and Lisa Yang

Abstract

We construct a publicly verifiable non-interactive delegation scheme for log-space uniform bounded depth computations in the common reference string (CRS) model, where the CRS is long (as long as the time it takes to do the computation). The soundness of our scheme relies on the assumption that there exists a group with a bilinear map, such that given group elements $g,h,h^t,h^{t^2},$ it is hard to output $g^a,g^b,g^c$ and $h^a,h^b,h^c$ such that $a \cdot t^2 + b \cdot t + c = 0$, but $a,b,c$ are not all zero. Previously, such a result was only known under knowledge assumptions (or in the Random Oracle model), or under non-standard assumptions related to obfuscation or zero-testable homomorphic encryption. We obtain our result by converting the interactive delegation scheme of Goldwasser, Kalai and Rothblum (J. ACM 2015) into a publicly verifiable non-interactive one. As a stepping stone, we give a publicly verifiable non-interactive version of the sum-check protocol of Lund, Fortnow, Karloff, Nisan (J. ACM 1992).

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
omerpa @ gmail com
History
2018-08-27: received
Short URL
https://ia.cr/2018/776
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/776,
      author = {Yael Kalai and Omer Paneth and Lisa Yang},
      title = {On Publicly Verifiable Delegation From Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/776},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/776}},
      url = {https://eprint.iacr.org/2018/776}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.