International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Non-Interactive Publicly-Verifiable Delegation of Committed Programs

Riddhi Ghosal , UCLA
Amit Sahai , UCLA
Brent Waters , UT Austin and NTT Research
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: 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}$.
  title={Non-Interactive Publicly-Verifiable Delegation of Committed Programs},
  author={Riddhi Ghosal and Amit Sahai and Brent Waters},