Authenticating Aggregate Range Queries over Dynamic Multidimensional Dataset.
Jia Xu · IACR Cryptology ePrint Archive · 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. Xu and Chang [1] proposed a new method to authenticate aggregate count query conditional on d-dimensional range selection over static dataset, with O(d logN) communication bits, where N is the number of points in the dataset D. We extend their method to suport other types of queires, including summing, finding of the minimum/maximum/median and usual (non-aggregate) range selection, with similar complexity. Furthermore, dynamic operations, like insertion and deletion, over the outsourced dataset are also supported.