Understand
In recent work, Cheu et al.
- (Eurocrypt 2019) proposed a protocol for $n$-party real summation in the shuffle model of differential privacy with $O_{\epsilon, \delta}(1)$ error and $\Theta(\epsilon\sqrt{n})$ one-bit messages per party.
- In contrast, every local model protocol for real summation must incur error $\Omega(1/\sqrt{n})$, and there exist protocols matching this lower bound which require just one bit of communication per party.
- Whether this gap in number of messages is necessary was left open by Cheu et al.
Built on
How to recycle random bits
Russell Impagliazzo and David Zuckerman · 1989
Earlier work this paper cites.
Cryptography from anonymity
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai · 2006
Earlier work this paper cites.
Privacy-preserving aggregation of time-series data
Elaine Shi, Richard Chow, T h. Hubert Chan, Dawn Song, and Eleanor Rieffel · 2011
Earlier work this paper cites.
Similar
Privacy for free: Posterior sampling and stochastic gradient monte carlo
Yu-Xiang Wang, Stephen E. Fienberg, and Alexander J. Smola · 2015
Cited alongside, same era.
A comprehensive comparison of multiparty secure additions with differential privacy
S. Goryczka and L. Xiong · 2017
Cited alongside, same era.
The privacy blanket of the shuffle model
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim · 2019
Cited alongside, same era.
Then
Distributed differential privacy via shuffling
Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev · 2019
Closest in time.
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…