Paper 2010/455

Optimal Verification of Operations on Dynamic Sets

Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos


We study the verification of \emph{set operations} in the model of \emph{authenticated data structures}, namely the problem of cryptographically checking the correctness of outsourced set operations performed by an untrusted \emph{server} over a dynamic collection of sets that are owned (and updated) by a trusted \emph{source}. We present a new authenticated data structure scheme that allows any entity to \emph{publicly} verify the correctness of primitive sets operations such as \emph{intersection}, \emph{union}, \emph{subset} and \emph{set difference}. Based on a novel extension of the security properties of \emph{bilinear-map accumulators} as well as on a primitive called \emph{accumulation tree}, our authenticated data structure is the first to achieve \emph{optimal} verification and proof complexity (i.e., only proportional to the size of the query parameters and the answer), as well as \emph{optimal} update complexity (i.e., constant), and without bearing any extra asymptotic space overhead. Queries (i.e., constructing the proof) are also efficient, adding a \emph{logarithmic} overhead to the complexity needed to compute the actual answer. In contrast, existing schemes entail high communication and verification costs or high storage costs as they recompute the query over authentic data or precompute answers to all possible queries. % Applications of interest include efficient verification of keyword search and database queries. We base the security of our constructions on the \emph{bilinear $q$-strong Diffie-Hellman} assumption.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
authenticated data structureslattice-based cryptography
Contact author(s)
cpap @ cs brown edu
2011-03-01: last of 4 revisions
2010-08-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charalampos Papamanthou and Roberto Tamassia and Nikos Triandopoulos},
      title = {Optimal Verification of Operations on Dynamic Sets},
      howpublished = {Cryptology ePrint Archive, Paper 2010/455},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.