Abstract: To solve the security and efficiency issues in the existing location privacy protection schemes, a location privacy protection scheme based on Markov chain technology for multi-value predictive query is proposed. First, the state transition matrix is used to calculate the input multiple query values, and generate the predicted position and the query content at the next moment. Then, Bloom filter technology is adopted to establish a caching mechanism for points of interest. Security analyses demonstrate that the proposed scheme satisfies security features such as anonymity, unforgeability, and is able to resist to query service tracking. Simulation results show that the proposed scheme has higher execution efficiency, lower communication costs, and a higher cache hit rate, which can effectively reduce the number of interactions with the location based service server.

Key words: location privacy, Markov chain, Bloom filter, cache