Efficient Secure and Verifiable Location-Based Skyline Queries over Encrypted Data

Supporting secure location-based services on encrypted data that is outsourced to cloud computing platforms remains an ongoing challenge for efficiency due to expensive ciphertext calculation overhead. Furthermore, since the clouds may not be trustworthy or even malicious, data security and result authenticity has caused huge concerns. Unfortunately, little work can enable query efficiency, dataset confidentiality and result authenticity to be commendably guaranteed. In this paper, we demonstrate the potential of supporting secure and verifiable location-based skyline queries (SVLSQ). First, we devise a novel and unified structure, named semi-blind R-tree (SR-tree), which protects the query unlinkability. Based on SR-tree, we propose an authenticated data structure, named secure and verifiable scope R-tree (SVSR-tree). Then, we develop several secure protocols based on SVSR-tree to accelerate the query efficiency and reduce the size of verification objects. Our method avoids compromising the privacy of datasets, queries, results and access patterns. Meanwhile, it authenticates the soundness and completeness of the skyline results while preserving privacy. Finally, we analyze the complexity and security of SVLSQ. Findings from the performance evaluation illustrate that SVLSQ is a dramatically efficient method in terms of query (no less than 3 orders of magnitude faster than other solutions) and verification.