Paper 2013/724

Verifiable Set Operations over Outsourced Databases

Ran Canetti, Omer Paneth, Dimitrios Papadopoulos, and Nikos Triandopoulos


We study the problem of verifiable delegation of computation over outsourced data, whereby a powerful worker maintains a large data structure for a weak client in a verifiable way. Compared to the well-studied problem of verifiable computation, this setting imposes additional difficulties since the verifier needs to verify consistency of updates succinctly and without maintaining large state. In particular,existing general solutions are far from practical in this setting. We present a scheme for verifiable evaluation of hierarchical set operations (unions, intersections and set-differences) applied to a collection of dynamically changing sets of elements from a given domain. That is, we consider two types of queries issued by the client: updates (insertions and deletions) and data queries, which consist of ``circuits'' of unions, intersections, and set-differences on the current collection of sets. This type of queries comes up in database queries, keyword search and numerous other applications, and indeed our scheme can be effectively used in such scenarios. The verification cost incurred is proportional only to the size of the final outcome set and to the size of the query, and is independent of the cardinalities of the involved sets. The cost of updates is optimal ($O(1)$ modular operations per update). Our construction extends that of [Papamanthou et al., Crypto 2011] and relies on a modified version of the \emph{extractable collision-resistant hash function} (ECRH) construction, introduced in [Bitansky et al., ITCS 2012] that can be used to succinctly hash univariate polynomials.

Available format(s)
Publication info
Preprint. Minor revision.
secure data outsourcingverifiable computationknowledge accumulatorssecure set operationsauthenticated query processingauthenticated data structures
Contact author(s)
dipapado @ bu edu
2013-11-07: received
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Omer Paneth and Dimitrios Papadopoulos and Nikos Triandopoulos},
      title = {Verifiable Set Operations over Outsourced Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2013/724},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.