Back to the Drawing Board: Revisiting the Design of Optimal Location Privacy-preserving Mechanisms
This work addresses the problem of ensuring comprehensive privacy protection in location-based services for users, highlighting that current optimal mechanisms are insufficient and incremental improvements are needed.
The paper revisits optimal location privacy-preserving mechanisms, showing that while existing strategies maximize adversary error, they vary in other privacy dimensions, and proposes a new mechanism maximizing conditional entropy while maintaining optimal adversary error, with empirical validation on real datasets.
In the last years we have witnessed the appearance of a variety of strategies to design optimal location privacy-preserving mechanisms, in terms of maximizing the adversary's expected error with respect to the users' whereabouts. In this work, we take a closer look at the defenses created by these strategies and show that, even though they are indeed optimal in terms of adversary's correctness, not all of them offer the same protection when looking at other dimensions of privacy. To avoid "bad" choices, we argue that the search for optimal mechanisms must be guided by complementary criteria. We provide two example auxiliary metrics that help in this regard: the conditional entropy, that captures an information-theoretic aspect of the problem; and the worst-case quality loss, that ensures that the output of the mechanism always provides a minimum utility to the users. We describe a new mechanism that maximizes the conditional entropy and is optimal in terms of average adversary error, and compare its performance with previously proposed optimal mechanisms using two real datasets. Our empirical results confirm that no mechanism fares well on every privacy criteria simultaneously, making apparent the need for considering multiple privacy dimensions to have a good understanding of the privacy protection a mechanism provides.