Time-Restricted, Verifiable, and Efficient Query Processing Over Encrypted Data on Cloud
Meng Li, Jianbo Gao, Liehuang Zhu, Zijian Zhang, Chhagan Lal, Mauro Conti · IEEE Transactions on Services Computing · 2023
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 addresstime-restricted accessorresult privacy, and randomly partition data items which degrades efficiency. In this article, we proposeTime-restricted,verifiable, andefficientQueryProcessing (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 proposecomplementary 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.