MARS: Enabling Verifiable Range-Aggregate Queries in Multi-Source Environments

The huge values created by Big Data and the recent advances in cloud computing have been driving data from different sources into cloud repositories for comprehensive query services. However, cloud-based data fusion makes it challenging to verify if an untrusted server faithfully integrates data and executes queries or not. This is even harder for range-aggregate queries that apply aggregate operations on data within given ranges. In this article, we propose a query authentication scheme, named MARS, enabling a user to efficiently authenticate range-aggregate queries on multi-source data. Specifically, MARS creates a VG-tree by subtly integrating Expressive Set Accumulator into a multi-dimensional G-tree while signing the root digest with a multi-source aggregate signature scheme. Compared with previous solutions, MARS has the following merits: (1) Practicality. Instead of treating range and aggregate queries separately, the user can directly verify the statistical result of selected data. (2) Scalability. Instead of authenticating the individual result from each source, the user can perform an aggregative validation on the integrated result from multiple sources. The experimental results demonstrate the effectiveness of MARS. For large-scale data fusion, the user-side verification time increases by only 103 ms as the amount of data sources increases by five times.