TY - GEN
T1 - Less is more
T2 - 44th IEEE Symposium on Security and Privacy, SP 2023
AU - Jiang, Kunming
AU - Chait-Roth, Devora
AU - Destefano, Zachary
AU - Walfish, Michael
AU - Wies, Thomas
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - R1CS-constraints
KW - SNARKs
KW - arithmetic-circuits
KW - front-ends
KW - probabilistic-proofs
KW - refinement-proofs
KW - verifiable-computation
KW - widgets
KW - zero-knowledge
UR - http://www.scopus.com/inward/record.url?scp=85166476519&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85166476519&partnerID=8YFLogxK
U2 - 10.1109/SP46215.2023.10179393
DO - 10.1109/SP46215.2023.10179393
M3 - Conference contribution
AN - SCOPUS:85166476519
T3 - Proceedings - IEEE Symposium on Security and Privacy
SP - 1112
EP - 1129
BT - Proceedings - 44th IEEE Symposium on Security and Privacy, SP 2023
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 22 May 2023 through 25 May 2023
ER -