CryptoDB
Optimal Authentication of Operations on Dynamic Sets
| Authors: | |
|---|---|
| Download: | |
| Abstract: | We study the problem of authenticating outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned by a trusted source. We present efficient methods for authenticating fundamental set operations, such as \emph{union} and \emph{intersection} so that the client can verify the correctness of the received answer. Based on a novel extension of the security properties of \emph{bilinear-map accumulators}, our authentication scheme is the first to achieve \emph{optimality} in several critical performance measures: (1) \emph{the verification overhead at the client is optimal}, that is, the client can verify an answer in time proportional to the size of the query parameters and answer; (2) \emph{the update overhead at the source is constant}; (3) \emph{the bandwidth consumption is optimal}, namely constant between the source and the server and operation-sensitive between the client and the server (i.e., proportional only to the size of the query parameters and the answer); and (4) \emph{the storage usage is optimal}, namely constant at the client and linear at the source and the server. Updates and queries are also efficient at the server. In contrast, existing schemes entail high bandwidth and verification costs or high storage usage since they recompute the query over authentic data or precompute answers to all possible queries. We also show applications of our techniques to the authentication of \emph{keyword searches} on outsourced document collections (e.g., inverted-index queries) and of queries in outsourced \emph{databases} (e.g., equi-join queries). Since set intersection is heavily used in these applications, we obtain new authentication schemes that compare favorably to existing approaches. |
BibTeX
@misc{eprint-2010-23356,
title={Optimal Authentication of Operations on Dynamic Sets},
booktitle={IACR Eprint archive},
keywords={authenticated data structures, accumulators, outsourced verifiable computation},
url={http://eprint.iacr.org/2010/455},
note={ cpap@cs.brown.edu 14845 received 23 Aug 2010, last revised 24 Aug 2010},
author={Charalampos Papamanthou and Roberto Tamassia and Nikos Triandopoulos},
year=2010
}