International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Satyanarayana V. Lokam

Publications

Year
Venue
Title
2023
PKC
Dew: A Transparent Constant-sized Polynomial Commitment Scheme
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.
2012
TCC
2008
CRYPTO

Program Committees