Understand
A protocol by Ishai et al.\ (FOCS 2006) showing how to implement distributed $n$-party summation from secure shuffling has regained relevance in the context of the recently proposed \emph{shuffle model} of differential privacy, as it allows to attain the accuracy levels of the curator model at a moderate communication cost.
- To achieve statistical security $2^{-\sigma}$, the protocol by Ishai et al.\ requires the number of messages sent by each party to {\em grow} logarithmically with $n$ as $O(\log n + \sigma)$.
- In this note we give an improved analysis achieving a dependency of the form $O(1+\sigma/\log n)$.
- Conceptually, this addresses the intuitive question left open by Ishai et al.\ of whether the shuffling step in their protocol provides a "hiding in the crowd" amplification effect as $n$ increases.
Built on
Cryptography from anonymity
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai · 2006
Earlier work this paper cites.
Prochlo: Strong privacy for analytics in the crowd
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnés, and Bernhard Seefeld · 2017
Earlier work this paper cites.
Similar
Differentially private summation with multi-message shuffling
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim · 2019
Cited alongside, same era.
Distributed differential privacy via shuffling
Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev · 2019
Cited alongside, same era.
Then
Amplification by shuffling: From local to central differential privacy via anonymity
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta · 2019
Closest in time.
Scalable and differentially private distributed aggregation in the shuffled model
Badih Ghazi, Rasmus Pagh, and Ameya Velingker · 2019
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…