Trajectory and Policy Aware Sender Anonymity in Location Based Services

摘要: We consider Location-based Service (LBS) settings, where a LBS provider logs the requests sent by mobile device users over period of time and later wants to publish/share these logs. Log sharing can be extremely valuable for advertising, data mining research network management, but it poses serious threat privacy users. Sender anonymity solutions prevent malicious attacker from inferring interests associating them with their service after gaining access anonymized With fast-increasing adoption smartphones concern that historic user trajectories are becoming more accessible, becomes necessary any sender solution protect against attackers trajectory-aware (i.e. have trajectories) as well policy-aware (i.e they know log anonymization policy). call such TP-aware. This paper introduces first guarantee TP-aware attackers, called k-anonymity. It turns out there many possible anonymizations same log, each different utility consumer log. The problem finding optimal is investigated. show trajectory-awareness renders computationally harder than trajectory-unaware variants found in literature (NP-complete size versus PTIME). describe PTIME l-approximation algorithm length l empirically scales large (up 2 million users).