On the Anonymization of Differentially Private Location Obfuscation
This work addresses privacy concerns for users of location-based services by enhancing anonymity in differentially private mechanisms, though it is incremental as it builds on existing geo-indistinguishability methods.
The paper tackles the problem of quantifying and improving anonymity in differentially private location obfuscation, showing that the optimal geo-indistinguishable mechanism provides stronger anonymity (more users satisfy k-anonymity) and better utility compared to the planar Laplacian mechanism.
Obfuscation techniques in location-based services (LBSs) have been shown useful to hide the concrete locations of service users, whereas they do not necessarily provide the anonymity. We quantify the anonymity of the location data obfuscated by the planar Laplacian mechanism and that by the optimal geo-indistinguishable mechanism of Bordenabe et al. We empirically show that the latter provides stronger anonymity than the former in the sense that more users in the database satisfy k-anonymity. To formalize and analyze such approximate anonymity we introduce the notion of asymptotic anonymity. Then we show that the location data obfuscated by the optimal geo-indistinguishable mechanism can be anonymized by removing a smaller number of users from the database. Furthermore, we demonstrate that the optimal geo-indistinguishable mechanism has better utility both for users and for data analysts.