### Publicly Verifiable Non-Interactive Arguments for Delegating Computation

Omer Paneth and Guy N. Rothblum

##### Abstract

We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier's running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings. All prior publicly verifiable non-interactive argument systems were based on non-falsifiable knowledge assumptions. Our new result builds on the beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who constructed privately verifiable 2-message arguments. While building on their techniques, our protocols avoid no-signaling PCPs, and we obtain a simplified and modular analysis. As a second contribution, we also construct a publicly verifiable non-interactive argument for (logspace-uniform) computations of bounded depth. The verifier's complexity grows with the depth of the circuit. This second protocol is adaptively sound, and its security is based on a falsifiable assumption about the hardness of a search problem on graded encodings (a milder cryptographic assumption). This result builds on the interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using graded encodings to construct a non-interactive version of their protocol.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
omerpa @ gmail com
History
Short URL
https://ia.cr/2014/981

CC BY

BibTeX

@misc{cryptoeprint:2014/981,
author = {Omer Paneth and Guy N.  Rothblum},
title = {Publicly Verifiable Non-Interactive Arguments for Delegating Computation},
howpublished = {Cryptology ePrint Archive, Paper 2014/981},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/981}},
url = {https://eprint.iacr.org/2014/981}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.