On the privacy offered by (k, δ)-anonymity
The widespread deployment of technologies with tracking capabilities, like GPS, GSM, RFID and on-line social networks, allows mass collection of spatio-temporal data about their users. As a consequence, several methods aimed at anonymizing spatio-temporal data before their publication have been proposed in recent years. Such methods are based on a number of underlying privacy models. Among these models, (k,Î´)-anonymity claims to extend the widely used k-anonymity concept by exploiting the spatial uncertainty Î´≥0 in the trajectory recording process. In this paper, we prove that, for any Î´>0 (that is, whenever there is actual uncertainty), (k,Î´)-anonymity does not offer trajectory k-anonymity, that is, it does not hide an original trajectory in a set of k indistinguishable anonymized trajectories. Hence, the methods based on (k,Î´)-anonymity, like Never Walk Alone (NWA) and Wait For Me (W4M) can offer trajectory k-anonymity only when Î´=0 (no uncertainty). Thus, the idea of exploiting the recording uncertainty Î´ to achieve trajectory k-anonymity with information loss inversely proportional to Î´ turns out to be flawed. âº (k,Î´)-Anonymity claims to provide trajectory k-anonymity. âº It exploits the spatial uncertainty Î´ of location recording. âº It aims to achieve information loss inversely proportional to Î´. âº We prove that, for any Î´>0, (k,Î´)-anonymity does not offer trajectory k-anonymity.