Non-Interactive Publicly-Verifiable Delegation of Committed Programs

Riddhi Ghosal; Amit Sahai; Brent Waters

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

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 should be convinced that they are receiving from the worker an actual computation of Alice's program on a given input . Before our work, the only object known to imply this challenging form of delegation was a SNARG/SNARK for . This is because from the point of view of the user/verifier, the program is an unknown witness to the computation. However, constructing a SNARG for 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 .

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: SNARGs Zero Knowledge
Contact author(s): riddhi @ cs ucla edu
sahai @ cs ucla edu
bwaters @ cs utexas edu
History: 2022-11-07: approved; 2022-11-02: received; See all versions
Short URL: https://ia.cr/2022/1508
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1508,
      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},
      url = {https://eprint.iacr.org/2022/1508}
}