Search locations safely and accurately: A location privacy protection algorithm with accurate service

Location-based applications provide convenient services to users. However, they also lead to location privacy leakage. Malicious adversaries may use the leaked information to violate users' privacy in unpredictable ways. Current location protection algorithms use fake or obfuscated locations to query services, thus resulting in inaccurate results. Usually, these algorithms need to sacrifice quality of service to ensure protection. Location searching services (LSSs) is one kind of location-based service (LBS). Users use LSSs to query nearby locations and exact distances to these locations. Thus, any mistake in results can make LSSs useless. Therefore, current location protection algorithms are not suitable for LSSs. In this paper, we propose a novel algorithm to offer protection for LSSs. In the proposed algorithm, users can have accurate LSSs with powerful location privacy protection. Overhead, in terms of data usage, was introduced in this paper to improve the privacy and decrease the Quality Loss (QL) simultaneously. QL can be decreased to zero if users have a good Internet environment. We derive the privacy and QL calculation methods and also use simulations to calculate the expected privacy and QL. The results illustrate that the proposed algorithm has excellent privacy protection and service quality.