Trading Optimality for Performance in Location Privacy

2017/10/16 by Chatzikokolakis, Konstantinos, Haddad, Serge, Kassem, Ali +1
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1710.05524

Abstract

Location-Based Services (LBSs) provide invaluable aid in the everyday activities of many individuals, however they also pose serious threats to the user' privacy. There is, therefore, a growing interest in the development of mechanisms to protect location privacy during the use of LBSs. Nowadays, the most popular methods are probabilistic, and the so-called optimal method achieves an optimal trade-off between privacy and utility by using linear optimization techniques. Unfortunately, due to the complexity of linear programming, the method is unfeasible for a large number n of locations, because the constraints are O(n³). In this paper, we propose a technique to reduce the number of constraints to O(n²), at the price of renouncing to perfect optimality. We show however that on practical situations the utility loss is quite acceptable, while the gain in performance is significant.

Related

• Prolonging the Hide-and-Seek Game: Optimal Trajectory Privacy for Location-Based Services
• A Framework for Managing Multifaceted Privacy Leakage While Optimizing Utility in Continuous LBS Interactions
• Ensuring Privacy in Location-Based Services: A Model-based Approach
• Back to the Drawing Board: Revisiting the Design of Optimal Location Privacy-preserving Mechanisms
• Privacy Preservation in Location-Based Services: A Novel Metric and Attack Model