Towards Privacy-Preserving Top-$k$k Location-Based Dominating Queries Over Encrypted Data

With the growth of cloud computing infrastructure, its cost-efficient paradigm is driving a growing wave of small and medium-sized enterprises to migrate data and services to cloud based platforms. However, due to privacy concerns, data encryption prior to outsourcing is an important means of protection, which in turn requires performing queries over the encrypted data. While several approaches do offer support for privacy preserving skyline or top-k queries, they typically struggle with efficiency when extended to secure top-k dominating queries, due to the inherent nature of combining the advantages of both top k and skyline queries. Nevertheless, this nature renders them as a more practical and promising alternative for location-based services. To address this, we introduce STLD, a secure top-k location-based dominating query scheme. Specifically, we develop an innovative index structure called Secure Aggregate R-tree (SAR-tree) by utilizing the Paillier cryptosystem and introducing meticulously crafted noise, while also incorporating principles from aggregate R-trees and semi-blind R-trees. Leveraging this structure, we propose a series of secure sub-protocols to facilitate top-k dominating queries, accompanied by optimization techniques to mitigate latency associated with computationally intensive dominating operations. Given an encrypted query, STLD not only efficiently answers the query but also guarantees the privacy of data(sets), results, queries and access patterns. Finally, STLD undergoes rigorous theoretical security and complexity analysis, complemented by empirical evaluations that demonstrate its performance and feasibility, achieving a reduction in query cost by 40%-60% compared to multiple competing methods.