Welcome to the resource topic for 2010/244
Title:
Authenticating Aggregate Range Queries over Dynamic Multidimensional Dataset
Authors: Jia XU
Abstract:We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set \set{D} of d-dimensional points, together with some authentication tag \set{T}, to an untrusted service provider Bob. Later, Alice issues some query over \set{D} to Bob, and Bob should produce a query result and a proof based on \set{D} and \set{T}. Alice wants to verify the integrity of the query result with the help of the proof, using only the private key. Xu J.~\emph{et al.}~\cite{maia-full} proposed an authentication scheme to solve this problem for multidimensional aggregate range query, including {\SUM, \COUNT, \MIN, \MAX} and {\MEDIAN}, and multidimensional range selection query, with O(d^2) communication overhead. However, their scheme only applys to static database. This paper extends their method to support dynamic operations on the dataset, including inserting or deleting a point from the dataset. The communication overhead of our scheme is O(d^2 \log N), where N is the number of data points in the dataset.
ePrint: https://eprint.iacr.org/2010/244
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .