Zero-knowledge accumulators and set algebra

Esha Ghosh, Olga Ohrimenko, Dimitrios Papadopoulos, Roberto Tamassia, Nikos Triandopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

26 Scopus citations

Abstract

Cryptographic accumulators allowto succinctly represent a set by an accumulation value with respect to which short (non-)membership proofs about the set can be efficiently constructed and verified. Traditionally, their security captures soundness but offers no privacy: Convincing proofs reliably encode set membership, but they may well leak information about the accumulated set. In this paper we put forward a strong privacy-preserving enhancement by introducing and devising zero-knowledge accumulators that additionally provide hiding guarantees: Accumulation values and proofs leak nothing about a dynamic set that evolves via element insertions/ deletions. We formalize the new property using the standard realideal paradigm, namely demanding that an adaptive adversary with access to query/update oracles, cannot tell whether he interacts with honest protocol executions or a simulator fully ignorant of the set (even of the type of updates on it). We rigorously compare the new primitive to existing ones for privacy-preserving verification of set membership (or other relations) and derive interesting implications among related security definitions, showing that zero-knowledge accumulators offer stronger privacy than recent related works by Naor et al. [TCC 2015] and Derler et al. [CT-RSA 2015]. We construct the first dynamic universal zeroknowledge accumulator that we show to be perfect zero-knowledge and secure under the q-Strong Bilinear Diffie-Hellman assumption. Finally, we extend our new privacy notion and our new construction to provide privacy-preserving proofs also for an authenticated dynamic set collection—a primitive for efficiently verifying more elaborate set operations, beyond set-membership. We introduce a primitive that supports a zero-knowledge verifiable set algebra: Succinct proofs for union, intersection and set difference queries over a dynamically evolving collection of sets can be efficiently constructed and optimally verified, while—for the first time—they leak nothing about the collection beyond the query result.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsJung Hee Cheon, Tsuyoshi Takagi
Pages67-100
Number of pages34
DOIs
StatePublished - 2016
Event22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10032 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016
Country/TerritoryViet Nam
CityHanoi
Period4/12/168/12/16

Keywords

  • Bilinear accumulators
  • Cloud privacy
  • Integrity
  • Outsourced computation
  • Privacy
  • Zero-knowledge dynamic and universal accumulators
  • Zero-knowledge set algebra
  • Zero-knowledge updates

Fingerprint

Dive into the research topics of 'Zero-knowledge accumulators and set algebra'. Together they form a unique fingerprint.

Cite this