Time-Restricted, Verifiable, and Efficient Query Processing over Encrypted Data on Cloud
Meng Li (Hefei University of Technology)
Jianbo Gao (Beijing Institute of Technology)
Liehuang Zhu (Beijing Institute of Technology)
Zijian Zhang (Beijing Institute of Technology)
Chhagan Lal (University of Padua)
M. Conti (TU Delft - Cyber Security, University of Padua)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Outsourcing data users' location data to a cloud server (CS) enables them to obtain kk 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 article, we propose Time-restricted, verifiable, and efficient Query Processing (TiveQP). TiveQP has three distinguishing features. 1) Expand SkNN: data users can query kk 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.