An Efficient and Privacy-Preserving Range Retrieval Scheme for Location-Based Services

With the rapid development of positioning technology and mobile devices, location-based services (LBS) have witnessed extensive adoption. However, privacy leakage issues have become increasingly severe. Existing solutions often focus solely on protecting users’ location privacy while neglecting query privacy requirements, and further exhibit suboptimal retrieval efficiency when handling large-scale datasets. To comprehensively preserve user and server privacy while enhancing data retrieval efficiency, this article proposes an efficient and privacy-preserving range retrieval scheme for LBSs (EPRL). The scheme proposes a Geohash-based query range generation algorithm, enabling users to generate query ranges according to their privacy requirements dynamically. To protect the user’s location privacy and query privacy, EPRL employs a ring signature policy. Furthermore, we innovatively design a Geohash-Trie Tree structure to store server data resources, effectively improving retrieval efficiency. Theoretical analysis and extensive experiments indicate that compared with other state-of-the-art LBS retrieval schemes, EPRL exhibits broader applicability, lower computational costs, and higher efficiency. When the number of ring signature users reaches 1000, the total computational overhead of the scheme is approximately 5 s, merely one-fifth of that required by similar schemes.