Enhancing Metric Privacy With a Shuffler
Authors: Andreas Athanasiou (INRIA and LIX, École Polytechnique), Konstantinos Chatzikokolakis (National and Kapodistrian University of Athens), Catuscia Palamidessi (INRIA and LIX, École Polytechnique)
Volume: 2025
Issue: 2
Pages: 650–679
DOI: https://doi.org/10.56553/popets-2025-0081
Abstract: Differential Privacy (DP) is one of the most successful privacy-preserving frameworks. In the central model of DP, a trusted server adds controlled noise as it acts as an interface between the data providers (users) and the data consumers (analysts). To overcome the strong trust assumption of having a trusted server, Local Differential Privacy (LDP) has been proposed, where the individual data are obfuscated directly at the end of the data provider. To improve LDP, in recent years researchers have proposed to combine it with a shuffler which is supposed to mix the data at the time of collection, enhancing the privacy of LDP without affecting utility. The shuffler is assumed to be trusted, but this is also an arguably strong assumption that cannot always be guaranteed. Metric privacy (aka d-privacy) is a variant of DP that can be applied in domains provided with a notion of distance, and it is particularly used in location privacy, where it takes the name of geo-indistinguishability. In contrast to DP, metric privacy allows calibrating the noise so that data points closer to the true one are more likely to be reported. In this work, we study how metric privacy can be improved by combining it with a shuffler. More specifically, we consider the combination of the shuffler with three mechanisms: Randomized Response, Geometric, and an optimal protocol, in the context of the sum and average queries. In all cases, we formally derive the relations that express the privacy amplification due to the shuffler, in terms of metric privacy. Moreover, we formally study the privacy guarantees of each protocol if the shuffler is compromised. Finally, we conduct experiments using synthetic data as well as real-world location data, showing that the proposed mechanisms achieve a better privacy-utility trade-off compared to the baseline of the standard geometric mechanism.
Keywords: Differential Privacy, Metric Privacy, Shuffle Model, Randomized Response, Geometric Mechanism
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
