Efficient Utility Improvement for Location Privacy

Authors: Konstantinos Chatzikokolakis (CNRS, Inria and LIX, École Polytechnique, France), Ehab ElSalamouny (Inria, France and Faculty of Computers and Informatics, Suez Canal University, Egypt), Catuscia Palamidessi (Inria and LIX, École Polytechnique, France)

Volume: 2017
Issue: 4
Pages: 308–328
DOI: https://doi.org/10.1515/popets-2017-0051

Download PDF

Abstract: The continuously increasing use of locationbased services poses an important threat to the privacy of users. A natural defense is to employ an obfuscation mechanism, such as those providing geoindistinguishability, a framework for obtaining formal privacy guarantees that has become popular in recent years. Ideally, one would like to employ an optimal obfuscation mechanism, providing the best utility among those satisfying the required privacy level. In theory optimal mechanisms can be constructed via linear programming. In practice, however, this is only feasible for a radically small number of locations. As a consequence, all known applications of geo-indistinguishability simply use noise drawn from a planar Laplace distribution. In this work, we study methods for substantially improving the utility of location obfuscation, while maintaining practical applicability as a main goal. We provide such solutions for both infinite (continuous or discrete) as well as large but finite domains of locations, using a Bayesian remapping procedure as a key ingredient. We evaluate our techniques in two real world complete datasets, without any restriction on the evaluation area, and show important utility improvements with respect to the standard planar Laplace approach.

Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.