MARS: Enabling Verifiable Range-Aggregate Queries in Multi-Source Environments
Qin Liu, Yu Peng, Qian Xu, Hongbo Jiang, Jie Wu, Tian Wang, Tao Peng, Guojun Wang, Shaobo Zhang
Abstract
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 paper, we propose a query authentication scheme, named <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math>${\sf MARS}$</tex-math></inline-formula> , enabling a user to efficiently authenticate range-aggregate queries on multi-source data. Specifically, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math>${\sf MARS}$</tex-math></inline-formula> 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, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math>${\sf MARS}$</tex-math></inline-formula> has the following merits: (1) <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Practicality.</i> Instead of treating range and aggregate queries separately, the user can directly verify the statistical result of selected data. (2) <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Scalability.</i> 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.