Paper 2013/724
Verifiable Set Operations over Outsourced Databases
Ran Canetti, Omer Paneth, Dimitrios Papadopoulos, and Nikos Triandopoulos
Abstract
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 (
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- secure data outsourcingverifiable computationknowledge accumulatorssecure set operationsauthenticated query processingauthenticated data structures
- Contact author(s)
- dipapado @ bu edu
- History
- 2013-11-07: received
- Short URL
- https://ia.cr/2013/724
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/724, 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}, url = {https://eprint.iacr.org/2013/724} }