Less is more: refinement proofs for probabilistic proofs

Kunming Jiang; Devora Chait-Roth; Zachary DeStefano; Michael Walfish; Thomas Wies

Paper 2022/1557

Less is more: refinement proofs for probabilistic proofs

Kunming Jiang, New York University, Carnegie Mellon University

Devora Chait-Roth, New York University

Zachary DeStefano, NYU

Michael Walfish, NYU

Thomas Wies, NYU

Abstract

There has been intense interest over the last decade in implementations of _probabilistic proofs_ (IPs, SNARKs, PCPs, and so on): protocols in which an untrusted party proves to a verifier that a given computation was executed properly, possibly in zero knowledge. Nevertheless, implementations still do not scale beyond small computations. A central source of overhead is the _front-end_: translating from the abstract computation to a set of equivalent arithmetic constraints. This paper introduces a general-purpose framework, called Distiller, in which a user translates to constraints not the original computation but an abstracted _specification_ of it. Distiller is the first in this area to perform such transformations in a way that is provably safe. Furthermore, by taking the idea of "encode a check in the constraints" to its literal logical extreme, Distiller exposes many new opportunities for constraint reduction, resulting in cost reductions for benchmark computations of 1.3–50, and in some cases, better asymptotics.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. 2023 IEEE Symposium on Security and Privacy (SP)
DOI: 10.1109/SP46215.2023.00142
Keywords: probabilistic proofs zero knowledge outsourced computation refinement proofs formal methods widgets gadgets R1CS
Contact author(s): kunmingj @ andrew cmu edu
dc4451 @ nyu edu
zd2131 @ nyu edu
mwalfish @ cs nyu edu
wies @ cs nyu edu
History: 2023-08-02: revised; 2022-11-09: received; See all versions
Short URL: https://ia.cr/2022/1557
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1557,
      author = {Kunming Jiang and Devora Chait-Roth and Zachary DeStefano and Michael Walfish and Thomas Wies},
      title = {Less is more: refinement proofs for probabilistic proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1557},
      year = {2022},
      doi = {10.1109/SP46215.2023.00142},
      url = {https://eprint.iacr.org/2022/1557}
}