ZAC: Efficient Zero-Knowledge Dynamic Universal Accumulator and Application to Zero-Knowledge Elementary Database

Abstract

—Zero-knowledge universal accumulator generates the succinct commitment to a set and produces the short (non) membership proof (universal) without leaking information about the set (zero-knowledge). In order to further support a generic set and zero-knowledge, existing techniques generally combine the zero-knowledge universal accumulator with other protocols, such as digital signatures and hashes to primes, which incur high overhead and may not be suitable for real-world use. It is desirable to commit a set of membership concealing the information with the optimal complexity. We devise ZAC, a new zero-knowledge Dynamic Universal Accumulator by taking the existing cryptographic primitives into account to produce a new efficient accumulator. Our underlying building blocks are Bloom Filter and vector commitment scheme in [19], utilizing the binary expression and aggregation to achieve efficiency, generic set support, zero-knowledge and universal properties. As a result, our scheme is improved in terms of proof size and proof time, also comparable to the RSA-based set accumulator in [8] in the verifying complexity. With 128 bit security, our proof size is 48 bytes while theirs is 1310 bytes and the running time of elliptic curve-based methods is faster than RSA-based counterpart. ZAC is proved to be complete, ϵ-sound and zero-knowledge. Extensively, based on ZAC as building block, we construct a new Zero-Knowledge Elementary Database (ZKEDB), which consumes 5 times less storage space, O(log N) less bandwidth, and O(log N) more efficient in proving and verification than the state-of-art work in [13] (where N is the domain space size). ZKEDB is proved to be complete, ϵ-sound and zero-knowledge. ZKEDB supports a new type of select top ℓ query, and can be extended to non-elementary databases.