International Association for Cryptologic Research

International Association
for Cryptologic Research


Dew: A Transparent Constant-sized Polynomial Commitment Scheme

Arasu Arun , New York University
Chaya Ganesh , Indian Institute of Science
Satya Lokam , Microsoft Research India
Tushar Mopuri , Indian Institute of Science
Sriram Sridhar , University of California, Berkeley
DOI: 10.1007/978-3-031-31371-4_19
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: We construct a polynomial commitment scheme with constant (i.e., independent of the degree) sized evaluation proofs and logarithmic (in the degree) verification time in the transparent setting. To the best of our knowledge, this is the first result achieving this combination of properties. We build our scheme from an inner product commitment scheme with constant-sized proofs but with linear verification time. To improve the verification time to logarithmic for polynomial commitments, we prove a new extremal combinatorial bound. Our constructions rely on groups of unknown order instantiated by class groups. We prove security of our constructions in the Generic Group Model. Compiling known information-theoretic proof systems using our polynomial commitment scheme yields transparent and constant-sized zkSNARKs (Zero-knowledge Succinct Non-interactive ARguments of Knowledge) with logarithmic verification.
  title={Dew: A Transparent Constant-sized Polynomial Commitment Scheme},
  author={Arasu Arun and Chaya Ganesh and Satya Lokam and Tushar Mopuri and Sriram Sridhar},