An Expressive (Zero-Knowledge) Set Accumulator

Yupeng Zhang, Jonathan Katz, Charalampos Papamanthou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a new construction of an expressive set accumulator. Unlike existing cryptographic accumulators, ours provides succinct proofs for a large collection of operations over accumulated sets, including intersection, union, set difference, SUM, COUNT, MIN, MAX, and RANGE, as well as arbitrary nestings of the above. We also show how to extend our accumulator to be zero-knowledge. The security of our accumulator is based on extractability assumptions and other assumptions that hold in the generic group model. Our construction has asymptotically optimal verification complexity and proof size, constant update complexity, and public verifiability/updatability - namely, any client who knows the public key and the last accumulator value can verify the supported operations and update the accumulator. The expressiveness of our accumulator comes at the cost of quadratic prover time. However, we show that the cryptographic operations involved are cheap compared to those incurred by generic approaches (e.g., SNARKs) that are equally expressive: our prover runs faster for sets of up to 5 million items. Our accumulator serves as a powerful cryptographic tool with many applications. For example, it can be applied to efficiently support verification of a rich collection of SQL queries when used as a drop-in replacement in existing verifiable database systems (e.g., IntegriDB, CCS 2015).

Original languageEnglish (US)
Title of host publicationProceedings - 2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages158-173
Number of pages16
ISBN (Electronic)9781509057610
DOIs
StatePublished - Jun 28 2017
Externally publishedYes
Event2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017 - Paris, France
Duration: Apr 26 2017Apr 28 2017

Publication series

NameProceedings - 2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017

Conference

Conference2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017
Country/TerritoryFrance
CityParis
Period4/26/174/28/17

Keywords

  • cryptographic accumulators
  • verifiable set operations
  • zero-knowledge accumulators

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Safety, Risk, Reliability and Quality
  • Law

Fingerprint

Dive into the research topics of 'An Expressive (Zero-Knowledge) Set Accumulator'. Together they form a unique fingerprint.

Cite this