Palamidessi.Optimal geo-indistinguishable mechanisms for location privacy.arXiv preprint arXiv:1402.5029

Abstract. With location-based services becoming increasingly more pop-ular, serious concerns are being raised about the potential privacy breaches that the disclosure of location information may induce. We consider two approaches that have been proposed to limit and control the privacy loss: one is the geo-indistinguishability notion of Andrés et al., which is inspired by differential privacy, and like the latter it is independent from the side knowledge of the adversary, and robust with respect to compo-sition of attacks. The other one is the mechanism of Shokri et al., which offers an optimal trade-off between the loss of quality of service and the privacy protection with respect to a given Bayesian adversary. We show that it is possible to combine the advantages of the two approaches: given a minimum threshold for the degree of geo-indistinguishability, we construct a mechanism that offers the maximal utility, as the solution of a linear program. Thanks to the fact that geo-indistinguishability is insensitive to the remapping of a Bayesian adversary, the mechanism so constructed is optimal also in the sense of Shokri et al. Furthermore we propose a method to reduce the number of constraints of the linear pro-gram from cubic to quadratic (with respect to the number of locations), maintaining the privacy guarantees without affecting significantly the utility of the generated mechanism. This lowers considerably the time required to solve the linear program, thus enlarging significantly the size of location sets for which the optimal trade-off mechanisms can still be computed.