The Price of Differential Privacy under Continual Observation
The Price of Differential Privacy under Continual Observation
复制标题
DOI：
--
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Palak Jain;Sofya Raskhodnikova;Satchit Sivakumar;Adam D. Smith
中科院分区：
文献类型：
--
作者：
Palak Jain;Sofya Raskhodnikova;Satchit Sivakumar;Adam D. Smith
在连续发布模型中，我们研究了差分私有机制的准确性。一个连续的释放机制接收一个敏感的数据集作为一个流的$T$输入，并产生，在接收每个输入后，一个准确的输出所获得的输入。相比之下，批处理算法将数据作为一个批次接收，并产生单个输出。我们提供了连续释放机制误差的第一个强下限。特别是，两个基本的问题，被广泛研究和使用的批处理模型，我们表明，每一个连续释放算法的最坏情况下的错误是$\tilde \Omega（T^{1/3}）$倍大于最好的批处理算法。以前的工作表明，在这两个模型中可实现的最坏情况误差之间只有多对数（以T$为单位）差距;此外，对于许多问题，包括二进制属性的总和，多对数差距是紧密的（Dwork等人，2010; Chan等人，2010年）。我们的研究结果表明，与求和密切相关的问题-特别是那些需要选择一组总和中最大的问题-在连续释放模型中比在批处理模型中更难。我们的下限仅假设隐私适用于预先固定的流（“非自适应”设置）。然而，我们提供了匹配的上限，保持在一个模型中的隐私是必要的，即使是自适应选择的流。这个模型可能是独立的兴趣。
We study the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sensitive dataset as a stream of $T$ inputs and produces, after receiving each input, an accurate output on the obtained inputs. In contrast, a batch algorithm receives the data as one batch and produces a single output. We provide the first strong lower bounds on the error of continual release mechanisms. In particular, for two fundamental problems that are widely studied and used in the batch model, we show that the worst case error of every continual release algorithm is $\tilde \Omega(T^{1/3})$ times larger than that of the best batch algorithm. Previous work shows only a polylogarithimic (in $T$) gap between the worst case error achievable in these two models; further, for many problems, including the summation of binary attributes, the polylogarithmic gap is tight (Dwork et al., 2010; Chan et al., 2010). Our results show that problems closely related to summation -- specifically, those that require selecting the largest of a set of sums -- are fundamentally harder in the continual release model than in the batch model. Our lower bounds assume only that privacy holds for streams fixed in advance (the"nonadaptive"setting). However, we provide matching upper bounds that hold in a model where privacy is required even for adaptively selected streams. This model may be of independent interest.