Paper 2010/050

Authenticating Aggregate Range Queries over Multidimensional Dataset

Jia XU and Ee-Chien CHANG


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 the 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 scheme that requires O(d^2 log^2 N) communication bits to authenticate an aggregate count query conditional on d-dimensional range selection, where N is the number of points in the dataset. The security of our scheme relies on Generalized Knowledge of Exponent Assumption proposed by Wu and Stinson [1]. The low communication bandwidth is achieved due to a new functional encryption scheme, which exploits a special property of BBG [2] HIBE scheme. Besides counting, our scheme can be extended to support summing, finding of the minimum and usual (non-aggregate) range selection with similar complexity, and the proposed approach potentially can be applied to other queries by using suitable functional encryption schemes.

Note: Minor update in presentation.

Available format(s)
Publication info
Published elsewhere. Not yet
AuthenticationMultidimensional Aggregate QuerySecure Outsourced DatabaseFunctional Encryption
Contact author(s)
jiaxu2001 @ gmail com
2011-03-22: last of 10 revisions
2010-01-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jia XU and Ee-Chien CHANG},
      title = {Authenticating  Aggregate  Range  Queries over Multidimensional Dataset},
      howpublished = {Cryptology ePrint Archive, Paper 2010/050},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.