We construct the first polynomial commitment scheme (PCS) that has a transparent setup, quasi-linear prover time, \(\log N\) verifier time, and \(\log \log N\) 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 \(N\le 2^{30}\) . 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: \({\textsf{PoKEMath}}\) , a protocol for efficiently proving that an arbitrary predicate over committed integer vectors holds; \(\textsf{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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

DewTwo: A Transparent PCS with Quasi-Linear Prover, Logarithmic Verifier and 4.5KB Proofs from Falsifiable Assumptions

  • Benedikt Bünz,
  • Tushar Mopuri,
  • Alireza Shirzad,
  • Sriram Sridhar

摘要

We construct the first polynomial commitment scheme (PCS) that has a transparent setup, quasi-linear prover time, \(\log N\) verifier time, and \(\log \log N\) 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 \(N\le 2^{30}\) . 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: \({\textsf{PoKEMath}}\) , a protocol for efficiently proving that an arbitrary predicate over committed integer vectors holds; \(\textsf{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.