Paper 2018/776
On Publicly Verifiable Delegation From Standard Assumptions
Yael Kalai, Omer Paneth, and Lisa Yang
Abstract
We construct a publicly verifiable noninteractive delegation scheme for logspace 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 nonstandard assumptions related to obfuscation or zerotestable homomorphic encryption. We obtain our result by converting the interactive delegation scheme of Goldwasser, Kalai and Rothblum (J. ACM 2015) into a publicly verifiable noninteractive one. As a stepping stone, we give a publicly verifiable noninteractive version of the sumcheck protocol of Lund, Fortnow, Karloff, Nisan (J. ACM 1992).
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 omerpa @ gmail com
 History
 20180827: received
 Short URL
 https://ia.cr/2018/776
 License

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} }