Connecting Robust Shuffle Privacy and Pan-Privacy

By Victor Balcer, Albert Cheu, Matthew Joseph, Jieming Mao. 2020

47 citations recorded by the source corpus.

In the \emph{shuffle model} of differential privacy, data-holding users send randomized messages to a secure shuffler, the shuffler permutes the messages, and the resulting collection of messages must be differentially private with regard to user data. In the \emph{pan-private} model, an algorithm processes a stream of data while maintaining an internal state that is differentially private with regard to the stream data. We give evidence connecting these two apparently different models. Our results focus on \emph{robustly} shuffle private protocols, whose privacy guarantees are not greatly affected by malicious users. First, we give robustly shuffle private protocols and upper bounds for counting distinct elements and uniformity testing. Second, we use pan-private lower bounds to prove robustly shuffle private lower bounds for both problems. Focusing on the dependence on the domain size $k$, we find that robust approximate shuffle privacy and approximate pan-privacy have additive error $\Theta(\sqrt{k})$ for counting distinct elements. For uniformity testing, we give a robust approximate shuffle private protocol with sample complexity $\tilde O(k^{2/3})$ and show that an $\Omega(k^{2/3})$ dependence is necessary for any robust pure shuffle private tester. Finally, we show that this connection is useful in both directions: we give a pan-private adaptation of recent work on shuffle private histograms and use it to recover further separations between pan-privacy and interactive local privacy.

Subfields: Artificial Intelligence, Privacy & Security, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

In Information Theory

Citations in the corpus

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “For more information on the shuffled model of DP, we refer the reader to Ghazi et al. (2020b; 2021; 2020c;a); Ishai et al. (2006); Balle et al. (2019; 2020); Balcer & Cheu (2020); Balcer et al. (2021); Girgis et al. (2020).”
Privacy Amplification by Decentralization (2020, background): “Connections between pan-privacy and the shuﬄe model have been recently studied (Balcer et al., 2020), allowing in some cases to adapt algorithms from one setting to the other.”
On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “In contrast with Theorem 4, Balcer et al. [5] recently gave a DP shuﬄe protocol for CountDistinct n,D with error O ( √ D ).”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Several works have also extended the study of shuffled model beyond simple aggregation tasks; for example, (Balcer et al., 2021; Chen et al., 2021) considers the count distinct problem whereas (Chang et al.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “Finally, [12] and [14] consider uniformity testing (a specific case of identity testing) under the notions of pan-privacy and shuffle privacy, respectively, which provide privacy guarantees in-between DP and LDP.”
Locally Private k-Means in One Round (2021, unknown): “…shuﬄe DP model includes work on aggregation (Balle et al., 2019; Ghazi et al., 2020d; Balle et al., 2020; Ghazi et al., 2021b), histograms and heavy hitters (Ghazi et al., 2021a; Balcer and Cheu, 2020; Ghazi et al., 2020a,c), and counting distinct elements (Balcer et al., 2021; Chen et al., 2021).”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “…tasks including computing histograms and heavy hitters (Ghazi et al., 2021a; Balcer & Cheu, 2020; Ghazi et al., 2020a;b; Cheu & Zhilyaev, 2021), counting distinct elements (Balcer et al., 2021; Chen et al., 2021) and private mean estimation (Girgis et al., 2021), as well as k -means clustering…”