[Resource Topic] 2022/1508: Non-Interactive Publicly-Verifiable Delegation of Committed Programs

Welcome to the resource topic for 2022/1508

Non-Interactive Publicly-Verifiable Delegation of Committed Programs

Authors: Riddhi Ghosal, Amit Sahai, Brent Waters


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

ePrint: https://eprint.iacr.org/2022/1508

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .