论文标题
纯粹的私人总和匿名消息
Pure Differentially Private Summation from Anonymous Messages
论文作者
论文摘要
改组（又名匿名）模型最近引起了人们对具有信任假设的候选隐私框架的重大兴趣，其信任假设比中心模型更好，但可实现的错误小于本地模型。我们在洗牌模型中研究纯差分私有（DP）协议，以供总结，这是一个基本且广泛使用的原始设备： - 对于二进制求和，每个用户中的每个用户都作为输入，我们提供了一个纯$ε$ -DP协议，用于估算用户持有的数量，最高$o_ε（1）$，每个用户都会发送$ o_is（\ log n）$。这是带有错误$ o（\ sqrt {n}）$的改组模型中的第一个纯协议。 使用此协议，我们提供了一个纯$ε$ -DP协议，该协议在$ [0，1] $中执行实数的总和至$o_ε（1）$的错误，并且每个用户在$ o_is（\ log^3 n）$ message $ o（\ log log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ n）$ bits中执行$o_ε（1）$。 - 相比之下，我们表明，对于具有绝对错误$ n^{0.5-ω（1）} $的任何纯$ε$ -DP协议，用于二进制求和的任何纯$ε$ -DP协议，每个用户通信必须至少为$ω__（\ sqrt {\ log n}）$ bits。这意味着（有界通信的）多消息洗牌模型与中心模型之间的第一个分离，以及在洗牌模型中纯和近似DP协议之间的第一个分离。 To prove our lower bound, we consider (a generalization of) the following question: given $γ$ in $(0, 1)$, what is the smallest m for which there are two random variables $X^0, X^1$ supported on $\{0, \dots ,m\}$ such that (i) the total variation distance between $X^0$ and $X^1$ is at least $1-γ$, and (ii) the moment generating $ x^0 $和$ x^1 $的功能在各处彼此的恒定因素之内？我们证明答案为$ m =θ（\ sqrt {\ log（1/γ）}）$。
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 errors smaller than the local model. We study pure differentially private (DP) protocols in the shuffled model for summation, a basic and widely used primitive: - For binary summation where each of n users holds a bit as an input, we give a pure $ε$-DP protocol for estimating the number of ones held by the users up to an error of $O_ε(1)$, and each user sends $O_ε(\log n)$ messages each of 1 bit. This is the first pure protocol in the shuffled model with error $o(\sqrt{n})$ for constant $ε$. Using this protocol, we give a pure $ε$-DP protocol that performs summation of real numbers in $[0, 1]$ up to an error of $O_ε(1)$, and where each user sends $O_ε(\log^3 n)$ messages each of $O(\log\log n)$ bits. - In contrast, we show that for any pure $ε$-DP protocol for binary summation in the shuffled model having absolute error $n^{0.5-Ω(1)}$, the per user communication has to be at least $Ω_ε(\sqrt{\log n})$ bits. This implies the first separation between the (bounded-communication) multi-message shuffled model and the central model, and the first separation between pure and approximate DP protocols in the shuffled model. To prove our lower bound, we consider (a generalization of) the following question: given $γ$ in $(0, 1)$, what is the smallest m for which there are two random variables $X^0, X^1$ supported on $\{0, \dots ,m\}$ such that (i) the total variation distance between $X^0$ and $X^1$ is at least $1-γ$, and (ii) the moment generating functions of $X^0$ and $X^1$ are within a constant factor of each other everywhere? We show that the answer is $m = Θ(\sqrt{\log(1/γ)})$.
