Paper 2022/1508

Non-Interactive Publicly-Verifiable Delegation of Committed Programs

Riddhi Ghosal, University of California, Los Angeles
Amit Sahai, University of California, Los Angeles
Brent Waters, The University of Texas at Austin

In this work, we present the first construction of a fully non-interactive publicly-verifiable delegation scheme for committed programs. More specifically, we consider a setting where Alice is a trusted author who delegates to an untrusted worker the task of hosting a program $P$, represented as a Boolean circuit. Alice also commits to a succinct value based on $P$. Any arbitrary user/verifier without knowledge of $P$ should be convinced that they are receiving from the worker an actual computation of Alice's program on a given input $x$. Before our work, the only object known to imply this challenging form of delegation was a SNARG/SNARK for $\mathcal{NP}$. This is because from the point of view of the user/verifier, the program $P$ is an unknown witness to the computation. However, constructing a SNARG for $\mathcal{NP}$ from standard assumptions remains a major open problem. In our work, we show how to achieve delegation in this challenging context assuming only the hardness of the Learning With Errors (LWE) assumption, bypassing the apparent need for a SNARG for $\mathcal{NP}$.

Available format(s)
Cryptographic protocols
Publication info
SNARGs Zero Knowledge
Contact author(s)
riddhi @ cs ucla edu
sahai @ cs ucla edu
bwaters @ cs utexas edu
2022-11-07: approved
2022-11-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Riddhi Ghosal and Amit Sahai and Brent Waters},
      title = {Non-Interactive Publicly-Verifiable Delegation of Committed Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1508},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.