Authenticating Aggregate Range Queries over Multidimensional Dataset.
Jia Xu, Ee‐Chien Chang · 2010
We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set D of d-dimensional points, together with some authentication tag T, to an untrusted service provider Bob. Later, Alice issues some query over D to Bob, and Bob should produce a query result and a proof based on D and 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 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.