Efficient and Privacy-Preserving Eclipse Query over Encrypted Data

As the mobile Internet grows rapidly, location-based services (LBSs) are widely applied in the tourism and transportation fields. To fully mine the data collected, location service providers (LSPs) intend to offer various query services to users, which include eclipse query. The eclipse query can generalize nearest neighbor queries and skyline queries and allow users to set more rough and customizable preference ranges. In addition, with the boom of cloud computing, more and more LSPs hope to leverage the cloud to offer better query services. Given that the data could potentially contain confidential information, the data are required to be encrypted prior to outsourcing them. Therefore, eclipse queries need to be executed on the ciphertext. Although several schemes for eclipse queries have been proposed in existing works, they have little focus on privacy issues. To address this issue, we propose an efficient and privacy-preserving scheme for eclipse queries (EPEQ) in this paper. First, we develop a MinValue tree to construct an index for the dataset. Then, by utilizing the MinValue tree and a symmetric homomorphic encryption technique, we design a secure minimum value comparison protocol to obtain a skyline data and a secure undominated data acquisition protocol to obtain the data not skyline dominated by the skyline data. After that, we present our scheme. We analyze the security of the EPEQ scheme and perform experimental evaluations, demonstrating the security and efficiency of our EPEQ scheme.