Paper 2017/337

Authentication of Outsourced Linear Function Query with Efficient Updates

Gang Sheng, Chunming Tang, Wei Gao, Yunlu Cai, and Xing Hu

Abstract

Storing the large-scale data on the cloud server side becomes nowadays an alternative for the data owner with the popularity and maturity of the cloud computing technique, where the data owner can manage the data with limited resources, and the user issues the query request to the cloud server instead of the data owner. As the server is not completely trusted, it is necessary for the user to perform results authentication to check whether or not the returned results from the cloud server are correct. We investigate in this paper how to perform efficient data update for the result authentication of the outsourced univariate linear function query. We seek to outsource almost all the data and computing to the server, and as few data and computations as possible are stored and performed on the data owner side, respectively. We present a novel scheme to achieve the security goal, which is divided into two parts. The first part is a verification algorithm for the outsourced computing of line intersections, which enables the data owner to store most of the data on the server side, and to execute less of the computing of the line intersections. The second part is an authentication data structure Two Level Merkle B Tree for the outsourced univariate linear function query, where the top level is used to index the user input and authenticate the query results, and the bottom level is used to index the query condition and authenticate the query results. The authentication data structure enables the data owner to update the data efficiently, and to implement the query on the server side. The theoretic analysis shows that our proposed scheme works with higher efficiency.