Paper 2010/244

Authenticating Aggregate Range Queries over Dynamic Multidimensional Dataset

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.

Note: Major update, since the based paper (eprint 2010/50) has been improved significantly.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
AuthenticationMultidimensional Aggregate QuerySecure Outsourced DatabaseDynamic DatabaseCountSumAverageMinMaxMedianRange Selection
Contact author(s)
jiaxu2001 @ gmail com
History
2011-03-29: last of 3 revisions
2010-05-02: received
See all versions
Short URL
https://ia.cr/2010/244
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/244,
      author = {Jia XU},
      title = {Authenticating  Aggregate  Range  Queries over Dynamic Multidimensional Dataset},
      howpublished = {Cryptology ePrint Archive, Paper 2010/244},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/244}},
      url = {https://eprint.iacr.org/2010/244}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.