Private summation in the multi-message shuffle model

B Balle, J Bell, A Gascón, K Nissim - Proceedings of the 2020 ACM …, 2020 - dl.acm.org
Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications …, 2020dl.acm.org
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 …
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.
ACM Digital Library
Showing the best result for this search. See all results