Private Summation in the Multi-Message Shuffle Model

By Borja Balle, James Bell, Adrià Gascón, Kobbi Nissim. 2020

121 citations recorded by the source corpus.

The shuffle model of differential privacy (Erlingsson et al. SODA 2019; Cheu et al. EUROCRYPT 2019) and its close relative encode-shuffle-analyze (Bittau et al. SOSP 2017) provide a fertile middle ground between the well-known local and central models. Similarly to the local model, the shuffle model assumes an untrusted data collector who receives privatized messages from users, but in this case a secure shuffler is used to transmit messages from users to the collector in a way that hides which messages came from which user. An interesting feature of the shuffle model is that increasing the amount of messages sent by each user can lead to protocols with accuracies comparable to the ones achievable in the central model. In particular, for the problem of privately computing the sum of n bounded real values held by n different users, Cheu et al. showed that O(sqrtn ) messages per user suffice to achieve O(1) error (the optimal rate in the central model), while Balle et al. (CRYPTO 2019) recently showed that a single message per user leads to Theta(n^1/3 ) MSE (mean squared error), a rate strictly in-between what is achievable in the local and central models. This paper introduces two new protocols for summation in the shuffle model with improved accuracy and communication trade-offs. Our first contribution is a recursive construction based on the protocol from Balle et al. mentioned above, providing poly(log log n) error with O(log log n) messages per user. The second contribution is a protocol with O(1) error and O(1) messages per user based on a novel analysis of the reduction from secure summation to shuffling introduced by Ishai et al. (FOCS 2006) (the original reduction required O(log n) messages per user). We also provide a numerical evaluation showing that our protocols provide good trade-offs between privacy, accuracy and communication for realistic values of n.

Subfields: Artificial Intelligence, Privacy & Security

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

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).”
Secure Single-Server Aggregation with (Poly)Logarithmic Overhead (2020, methodology): “This primitive is the basis of the shuffle model of differential privacy [3, 4, 11, 19] and could be used for anonymized submissions [6].”
Private Aggregation from Fewer Anonymous Messages (2019, neutral): “[2,5] obtained an upper bound that is asymptotically the same as the one in Theorem 1.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, background): “Balle, Bell, Gascón and Nissim [10] discussed the effect of malicious users on the accuracy guarantee of a shuffle protocol.”
Locally Private k-Means in One Round (2021, methodology): “…an input sequence x ∈ X n , we let S Enc Recent research on the 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…”
A Survey on Differential Privacy for Unstructured Data Content (2022, methodology): “[5] proposed shuffled DP mechanisms to improve data utility within smallscale dataset scenarios.”