Enhancing Metric Privacy With a Shuffler

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.