“Don’t trust anyone”: Privacy protection for location-based services

We present a decentralized approach that exploits the capability of mobile devices to form wireless personal ad-hoc networks in order to protect the privacy of users who access location-based services. The novelty of our approach is that users do not need to trust any party such as an intermediary server or peers with their locations and identities. We propose efficient algorithms for users to compute a kk-anonymous imprecise location and to randomly select one of her peers with uniform probability who forwards the service request on behalf of the user. Our experimental evaluation shows that using our approach a user can enjoy a high quality of service with a high degree of privacy.