PRIVIC: A privacy-preserving method for incremental collection of location data. (arXiv:2206.10525v3 [cs.CR] UPDATED)

With advancements in technology, the threats to the privacy of sensitive data
(e.g. location data) are surging. A standard method to mitigate the privacy
risks for location data is by adding noise to the true values to achieve
geo-indistinguishability. However, we argue that geo-indistinguishability alone
is insufficient to cover all privacy concerns. In particular, isolated
locations are not protected by the state-of-the-art Laplace mechanism (LAP) for
geo-indistinguishability. We focus on a mechanism that is generated by the
Blahut-Arimoto algorithm (BA) from rate-distortion theory. We show that BA, in
addition to providing geo-indistinguishability, enforces an elastic metric that
ameliorates the issue of isolation. We then study the utility of BA in terms of
the statistical precision that can be derived from the reported data, focusing
on the inference of the original distribution. To this purpose, we apply the
iterative Bayesian update (IBU), an instance of the famous
expectation-maximization method from statistics, that produces the most likely
distribution for any obfuscation mechanism. We show that BA harbours a better
statistical utility than LAP for high privacy and becomes comparable as privacy
decreases. Remarkably, we point out that BA and IBU, two seemingly unrelated
methods that were developed for completely different purposes, are dual to each
other. Exploiting this duality and the privacy-preserving properties of BA, we
propose an iterative method, PRIVIC, for a privacy-friendly incremental
collection of location data from users by service providers. In addition to
extending the privacy guarantees of geo-indistinguishability and retaining a
better statistical utility than LAP, PRIVIC also provides an optimal trade-off
between information leakage and quality of service. We illustrate the soundness
and functionality of our method both analytically and with experiments.