Secure, Available, Verifiable, and Efficient Range Query Processing on Outsourced Datasets

Range queries allow data users to outsource their data to a Cloud Server (CS) that responds to data users who submit a request with range conditions. However, security concerns hinder the wide-scale adoption. Existing works neglect item availability, fail to protect secure verification or sacrifice search accuracy for efficiency. In this paper, we propose Secure, Available, Verifiable, and Efficient (SAVE) range query processing, which has three distinctive features. (1) Secure availability checking against a malicious CS: we design a keyed index-based secure verification mechanism to check the availability of matched nodes, including validity and freshness. (2) Secure result verification: we design a targeted verification mechanism for result correctness and completeness while not compromising security. (3) Improved efficiency and accuracy: we design a lay-ered encoding method to improve search efficiency and accuracy. We formally stated and proved the security of SAVE in the random oracle model. We conducted extensive experiments over the Yelp and FourSquare dataset to validate the efficiency, e.g., a query over 10 thousand data items only needs 19.4 ms to get queried results and 3.5 ms for local verification.