Optimal geo-indistinguishable mechanisms for location privacy

Nicholás E. Bordenabe; Konstantinos Chatzikokolakis; Catuscia Palamidessi

doi:10.1145/2660267.2660345

Optimal geo-indistinguishable mechanisms for location privacy

Nicholás E. Bordenabe, Konstantinos Chatzikokolakis, Catuscia Palamidessi

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

107 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 2014 ACM SIGSAC conference on computer and communications security
Place of Publication	New York, N.Y.
Publisher	ACM
Pages	251-262
Number of pages	12
ISBN (Print)	9781450332392
DOIs	https://doi.org/10.1145/2660267.2660345
Publication status	Published - 2014
Externally published	Yes
Event	ACM conference on computer and communications security (21st : 2014) - Arizona, USA Duration: 3 Nov 2014 → 7 Nov 2014

Conference

Conference	ACM conference on computer and communications security (21st : 2014)
City	Arizona, USA
Period	3/11/14 → 7/11/14

Keywords

Location privacy
Location obfuscation
Geo-indistinguishability
Differential privacy
Linear optimization

Access to Document

10.1145/2660267.2660345

Fingerprint Dive into the research topics of 'Optimal geo-indistinguishable mechanisms for location privacy'. Together they form a unique fingerprint.

Cite this

Bordenabe, N. E., Chatzikokolakis, K., & Palamidessi, C. (2014). Optimal geo-indistinguishable mechanisms for location privacy. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security (pp. 251-262). New York, N.Y.: ACM. https://doi.org/10.1145/2660267.2660345

@inproceedings{e0690580693a4f21b2a7db58087ba41d,

title = "Optimal geo-indistinguishable mechanisms for location privacy",

abstract = "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.",

keywords = "Location privacy, Location obfuscation, Geo-indistinguishability, Differential privacy, Linear optimization",

author = "Bordenabe, {Nichol{\'a}s E.} and Konstantinos Chatzikokolakis and Catuscia Palamidessi",

year = "2014",

doi = "10.1145/2660267.2660345",

language = "English",

isbn = "9781450332392",

pages = "251--262",

booktitle = "Proceedings of the 2014 ACM SIGSAC conference on computer and communications security",

publisher = "ACM",

}

Bordenabe, NE, Chatzikokolakis, K & Palamidessi, C 2014, Optimal geo-indistinguishable mechanisms for location privacy. in Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. ACM, New York, N.Y., pp. 251-262, ACM conference on computer and communications security (21st : 2014), Arizona, USA, 3/11/14. https://doi.org/10.1145/2660267.2660345

Optimal geo-indistinguishable mechanisms for location privacy. / Bordenabe, Nicholás E.; Chatzikokolakis, Konstantinos; Palamidessi, Catuscia.

Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. New York, N.Y. : ACM, 2014. p. 251-262.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

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

U2 - 10.1145/2660267.2660345

DO - 10.1145/2660267.2660345

M3 - Conference proceeding contribution

SN - 9781450332392

SP - 251

EP - 262

BT - Proceedings of the 2014 ACM SIGSAC conference on computer and communications security

PB - ACM

CY - New York, N.Y.

ER -