Paper 2025/129

DewTwo: a transparent PCS with quasi-linear prover, logarithmic verifier and 4.5KB proofs from falsifiable assumptions

Benedikt Bünz, New York University
Tushar Mopuri, University of Pennsylvania
Alireza Shirzad, University of Pennsylvania
Sriram Sridhar, University of California, Berkeley
Abstract

We construct the first polynomial commitment scheme (PCS) that has a transparent setup, quasi-linear prover time, logN verifier time, and loglogN proof size, for multilinear polynomials of size N. Concretely, we have the smallest proof size amongst transparent PCS, with proof size less than 4.5KB for N230. We prove that our scheme is secure entirely under falsifiable assumptions about groups of unknown order. The scheme significantly improves on the prior work of Dew (PKC 2023), which has super-cubic prover time and relies on the Generic Group Model (a non-falsifiable assumption). Along the way, we make several contributions that are of independent interest: PoKEMath, a protocol for efficiently proving that an arbitrary predicate over committed integer vectors holds; SIPA, a bulletproofs-style inner product argument in groups of unknown order; we also distill out what prior work required from the Generic Group Model and frame this as a falsifiable assumption.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
SNARKPolynomial Commitment SchemeGroups of unknown order
Contact author(s)
bb @ nyu edu
tmopuri @ upenn edu
alrshir @ upenn edu
srirams @ berkeley edu
History
2025-01-28: approved
2025-01-27: received
See all versions
Short URL
https://ia.cr/2025/129
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/129,
      author = {Benedikt Bünz and Tushar Mopuri and Alireza Shirzad and Sriram Sridhar},
      title = {{DewTwo}: a transparent {PCS} with quasi-linear prover, logarithmic verifier and 4.{5KB} proofs from falsifiable assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/129},
      year = {2025},
      url = {https://eprint.iacr.org/2025/129}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.