Paper 2010/455
Optimal Verification of Operations on Dynamic Sets
Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos
Abstract
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
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- authenticated data structureslattice-based cryptography
- Contact author(s)
- cpap @ cs brown edu
- History
- 2011-03-01: last of 4 revisions
- 2010-08-24: received
- See all versions
- Short URL
- https://ia.cr/2010/455
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2010/455, 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}, url = {https://eprint.iacr.org/2010/455} }