Collusion-resistant query anonymization for location-based services

We address the problem of anonymizing user queries when accessing location-based services. We design a novel location and query anonymization protocol called MAZE that preserves the user privacy without relying on trusted parties. MAZE guarantees the user's anonymity and privacy in a decentralized manner using P2P groups. Compared to prior works, MAZE enables individual user authentication for the purpose of implementing a pay-peruse or membership subscription model and is resistant to collusion of the P2P users. We extend MAZE to L-MAZE, a multi-stage protocol that is resistant to collusion of the P2P users with the LBS, at the expense of higher communication overhead.