文章基本信息
- 标题：Pure Differentially Private Summation from Anonymous Messages
- 本地全文：下载
- 作者：Badih Ghazi ; Noah Golowich ; Ravi Kumar 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：163
- 页码：15:1-15:23
- DOI：10.4230/LIPIcs.ITC.2020.15
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically: - For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-differentially private protocol for estimating the number of ones held by the users up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log n) one-bit messages. This is the first pure protocol in the shuffled model with error o(â^Sn) for constant values of ε. Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers in [0, 1] up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log³ n) messages each consisting of O(log log n) bits. - In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n^{0.5-Ω(1)}, the per user communication has to be at least Ω_{ε}(â^S{log n}) bits. This implies (i) the first separation between the (bounded-communication) multi-message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model. Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question that might be of independent interest: given γ â^^ (0, 1), what is the smallest positive integer m for which there exist two random variables Xâ° and X^1 supported on {0, ⦠, m} such that (i) the total variation distance between Xâ° and X^1 is at least 1 - γ, and (ii) the moment generating functions of Xâ° and X^1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Î~(â^S{log(1/γ)}).
- 关键词：Pure differential privacy; Shuffled model; Anonymous messages; Summation; Communication bounds
