We propose a new commitment scheme for key-value maps whose size does not grow with the number of keys, yet proofs of membership are of constant-size. In fact, both the encoding and the proofs consist of just two and three group elements respectively (in groups of unknown order like class groups). Verifying and updating proofs involves just a few group exponentiations. Additive updates to key values enjoy the same level of efficiency too.
Key-value commitments can be used to build dynamic accumulators and vector commitments, which find applications in group signatures, anonymous credentials, verifiable databases, interactive oracle proofs, etc. Using our new key-value commitment, we provide the most efficient constructions of (sub)vector commitments to date.
Category / Keywords: cryptographic protocols / commitments, accumulators, blockchains, key-value, efficient, RSA Original Publication (with minor differences): IACR-ASIACRYPT-2020 Date: received 23 Sep 2020, last revised 5 Oct 2020 Contact author: srini131293 at gmail com, shashank agraval@gmail com Available format(s): PDF | BibTeX Citation Note: Minor edits. Version: 20201005:220335 (All versions of this report) Short URL: ia.cr/2020/1161