Time-Restricted, Verifiable, and Efficient Query Processing over Encrypted Data on Cloud

Outsourcing data users' location data to a cloud server (CS) enables them to obtain k nearest points of interest. However, data users' privacy concerns hinder the wide-scale use. Several studies have achieved Secure k Nearest Neighbor (SkNN) query, but do not address time-restricted access or result privacy, and randomly partition data items which degrades efficiency. In this paper, we propose Time-restricted, verifiable, and efficient Query Processing (TiveQP). TiveQP has three distinguishing features. (1) Expand SkNN: data users can query k nearest locations open at a specific time. (2) Adopt a stronger threat model: we assume the CS is malicious and propose complementary set (i.e., transform proving “in” a set to proving “in” its complementary set) to allow data users to verify results without leaking unqueried data items' information. (3) Improve efficiency: we design a space encoding technique and a pruning strategy to improve efficiency in query processing and result verification. We formally proved the security of TiveQP in the random oracle model. We conducted extensive evaluations over a Yelp dataset to show that TiveQP significantly improves over existing work, e.g., top-10NN query over 100 thousand data items only needs 10 ms to get queried results and 1.4 ms for verification.