International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Authenticating Aggregate Range Queries over Dynamic Multidimensional Dataset

Authors:
Jia XU
Download:
URL: http://eprint.iacr.org/2010/244
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23145,
  title={Authenticating  Aggregate  Range  Queries over Dynamic Multidimensional Dataset},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Authentication, Multidimensional Aggregate Query, Dynamic Database, Secure Outsourced Database, Provable Remote Computing},
  url={http://eprint.iacr.org/2010/244},
  note={ jiaxu2001@gmail.com 14728 received 29 Apr 2010},
  author={Jia XU},
  year=2010
}