TY - GEN
T1 - Optimal geo-indistinguishable mechanisms for location privacy
AU - Bordenabe, Nicholás E.
AU - Chatzikokolakis, Konstantinos
AU - Palamidessi, Catuscia
PY - 2014
Y1 - 2014
N2 - We consider the geo-indistinguishability approach to location privacy, and the trade-off with respect to utility. We show that, given a desired degree of geo-indistinguishability, it is possible to construct a mechanism that minimizes the service quality loss, using linear programming techniques. In addition we show that, under certain conditions, such mechanism also provides optimal privacy in the sense of Shokri et al. Furthermore, we propose a method to reduce the number of constraints of the linear program from cubic to quadratic, maintaining the privacy guarantees and without affecting significantly the utility of the generated mechanism. This reduces considerably the time required to solve the linear program, thus enlarging significantly the location sets for which the optimal mechanisms can be computed.
AB - We consider the geo-indistinguishability approach to location privacy, and the trade-off with respect to utility. We show that, given a desired degree of geo-indistinguishability, it is possible to construct a mechanism that minimizes the service quality loss, using linear programming techniques. In addition we show that, under certain conditions, such mechanism also provides optimal privacy in the sense of Shokri et al. Furthermore, we propose a method to reduce the number of constraints of the linear program from cubic to quadratic, maintaining the privacy guarantees and without affecting significantly the utility of the generated mechanism. This reduces considerably the time required to solve the linear program, thus enlarging significantly the location sets for which the optimal mechanisms can be computed.
KW - Location privacy
KW - Location obfuscation
KW - Geo-indistinguishability
KW - Differential privacy
KW - Linear optimization
UR - http://www.scopus.com/inward/record.url?scp=84910607722&partnerID=8YFLogxK
U2 - 10.1145/2660267.2660345
DO - 10.1145/2660267.2660345
M3 - Conference proceeding contribution
SN - 9781450332392
SN - 9781450329576
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 251
EP - 262
BT - Proceedings of the 2014 ACM SIGSAC conference on computer and communications security
PB - Association for Computing Machinery
CY - New York, N.Y.
T2 - ACM conference on computer and communications security (21st : 2014)
Y2 - 3 November 2014 through 7 November 2014
ER -