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

Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha
Published: 2021-09-27

Source: https://arxiv.org/abs/2109.13158

PDF: https://arxiv.org/pdf/2109.13158

Labels Predicted by AI

アルゴリズム データプライバシー評価 プライバシーリスク管理

Please note that these labels were automatically added by AI. Therefore, they may not be entirely accurate.
For more details, please see the About the Literature Database page.

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 the central model, while each user only sends 1 + o(1) short messages in expectation.