Policy-Aware Sender Anonymity in Location Based Services

A location-based service (LBS) broker answers the requests of mobile device users for services in their proximity (e.g. "find the nearest gas station", "theater", "restaurant", etc.). For privacy reasons, the request sender wishes to hide her identity even from attackers who (via hacking or subpoenas) gain access to the request (from the broker's log) and to the location of the mobile user at the time of the request (from the phone company). Recent research proposes a privacy guarantee called "sender k-anonymity", by which the request and location logs are insufficient to distinguish among the actual sender and k-1 other possible senders. Typical k-anonymization algorithms include in the request a cloaking area around the sender instead of her precise location. This area is chosen to include at least k-1 other mobile users. To maximize the utility of the answer to the service request, the cloaking area is minimized. We show that, while these solutions achieve k-anonymity against attackers who are unaware of the utility-maximization policy, policy-aware attackers can violate k-anonymity. We introduce and formalize the class of policy-aware attackers and define a novel, stronger privacy guarantee: sender k-anonymity against policy-aware attackers. We study the problem of finding, among several policy-aware k-anonymizations of a set of mobile users, the one with maximal utility. We find that when the cloaking areas are allowed to partially overlap, the problem is NP-complete, but becomes PTIME when the cloaking areas are quadrants of a quad-tree-based partition of the map (a common choice in many anonymization solutions, including the reference system Casper). We implement and evaluate our policy-aware anonymization algorithm experimentally, showing that it scales well with the number of mobile users and their degree of mobility, and that the utility reduction traded for the stronger privacy guarantee is reasonable.