Zero-Knowledge Accumulators and Set Operations
Esha Ghosh, Olga Ohrimenko, Dimitrios N. Papadopoulos, Roberto Tamassia, Nikos Triandopoulos · 2016
Abstract. Accumulators provide a way to succinctly represent a set with elements drawn from a given domain, us-ing an accumulation value. Subsequently, short proofs for the set-membership (or non-membership) of any element from the domain can be constructed and efficiently verified with respect to this accumulation value. Accumula-tors have been widely studied in the literature, primarily, as an authentication primitive: a malicious prover (e.g., an untrusted server) should not be able to provide convincing proofs on false statements (e.g., successfully prove membership for a value not in the set) to a verifier that issues membership queries (of course, having no access to set itself). In essence, in existing constructions the accumulation value acts as a (honestly generated) “commitment” to the set that allows selective “opening ” as specified by membership queries—but with no “hiding ” properties. In this paper we revisit this primitive and propose a privacy-preserving enhancement. We define the notion of a zero-knowledge accumulator that provides the following very strong privacy notion: Accumulation values and proofs constructed during the protocol execution leak nothing about the set itself, or any subsequent updates to it (i.e., via element insertions/deletions). We formalize this property by a standard real/ideal execution game. An adversarial party that is allowed to choose the set and is given access to query and update oracles, cannot distinguish whether this interaction takes place with respect to the honestly executed algorithms of the scheme or with a simulator that is not given access to the set itself (and for updates, it does not even learn the type of update