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 of -dimensional points, together with some authentication tag , to an untrusted service provider Bob. Later, Alice issues some query over to Bob, and Bob should produce a query result and a proof based on and . 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 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 , where 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},
      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.