Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:3692-3701, 2021.

Abstract

The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work, we study the problem of summing (aggregating) real numbers or integers, a basic primitive in numerous machine learning tasks, in the shuffle model. We give a protocol achieving error arbitrarily close to that of the (Discrete) Laplace mechanism in central differential privacy, while each user only sends 1 + o(1) short messages in expectation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-ghazi21a, title = {Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message}, author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Pagh, Rasmus and Sinha, Amer}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {3692--3701}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/ghazi21a/ghazi21a.pdf}, url = {https://proceedings.mlr.press/v139/ghazi21a.html}, abstract = {The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work, we study the problem of summing (aggregating) real numbers or integers, a basic primitive in numerous machine learning tasks, in the shuffle model. We give a protocol achieving error arbitrarily close to that of the (Discrete) Laplace mechanism in central differential privacy, while each user only sends 1 + o(1) short messages in expectation.} }
Endnote
%0 Conference Paper %T Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message %A Badih Ghazi %A Ravi Kumar %A Pasin Manurangsi %A Rasmus Pagh %A Amer Sinha %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-ghazi21a %I PMLR %P 3692--3701 %U https://proceedings.mlr.press/v139/ghazi21a.html %V 139 %X The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work, we study the problem of summing (aggregating) real numbers or integers, a basic primitive in numerous machine learning tasks, in the shuffle model. We give a protocol achieving error arbitrarily close to that of the (Discrete) Laplace mechanism in central differential privacy, while each user only sends 1 + o(1) short messages in expectation.
APA
Ghazi, B., Kumar, R., Manurangsi, P., Pagh, R. & Sinha, A.. (2021). Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:3692-3701 Available from https://proceedings.mlr.press/v139/ghazi21a.html.

Related Material