CryptoDB
Satyanarayana V. Lokam
Publications
Year
Venue
Title
2023
PKC
Dew: A Transparent Constant-sized Polynomial Commitment Scheme
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.
Program Committees
Coauthors
- Arasu Arun (1)
- Raghav Bhaskar (1)
- Chaya Ganesh (1)
- Sanjam Garg (1)
- Vipul Goyal (1)
- Virendra Kumar (1)
- Satyanarayana V. Lokam (3)
- Mohammad Mahmoody (1)
- Tushar Mopuri (1)
- Sriram Sridhar (1)