International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Authenticating Aggregate Range Queries over Multidimensional Dataset

Jia XU
Ee-Chien CHANG
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 $\mathtt{D}$ of $d$-dimensional points, together with some authentication tag $\mathtt{T}$, to an untrusted service provider Bob. Later, Alice issues some query over $\mathtt{D}$ to Bob, and Bob should produce a query result and a proof based on $\mathtt{D}$ and $\mathtt{T}$. Alice wants to verify the integrity of the query result with the help of the proof, using only the private key. In this paper, we consider aggregate query conditional on multidimensional range selection. In its basic form, a query asks for the total number of data points within a $d$-dimensional range. We are concerned about the number of communication bits required and the size of the tag $\mathtt{T}$. We give a method that requires $O(d^2)$ communication bits to authenticate an aggregate query conditional on $d$-dimensional range selection. Besides counting, summing and finding of the minimum can also be supported. Furthermore, our scheme can be extended slightly to authenticate $d$-dimensional usual (non-aggregate) range selection query with $O(d^2)$ bits communication overhead, improving known results that require $O(\log^{d-1} N)$ communication overhead, where $N$ is the number of data points in the dataset.
  title={Authenticating  Aggregate  Range  Queries over Multidimensional Dataset},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Authentication, Aggregate Query, Range Selection Query, Database Outsourcing},
  note={Not yet 14728 received 31 Jan 2010, last revised 29 Apr 2010},
  author={Jia XU and Ee-Chien CHANG},