Local Differential Privacy for Evolving Data
Local Differential Privacy for Evolving Data
复制标题
DOI：
10.29012/jpc.718
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Matthew Joseph;Aaron Roth;Jonathan Ullman;Bo Waggoner
中科院分区：
文献类型：
--
作者：
Matthew Joseph;Aaron Roth;Jonathan Ullman;Bo Waggoner
现在有一些大规模的差分隐私部署，用于收集有关用户的统计信息。然而，这些部署会定期重新收集数据并使用专为一次性使用设计的算法重新计算统计数据。因此，这些系统无法在长期范围内提供有意义的隐私保证。此外，减轻这种影响的现有技术不适用于这些系统使用的差异隐私的“本地模型”。在本文中，我们引入了一种用于本地差分隐私的新技术，该技术使得随着时间的推移保持最新的统计数据成为可能，并且隐私保证仅在基础分布的变化数量而不是收集周期的数量上降低。我们使用我们的技术来跟踪设置中不断变化的统计数据，其中用户被划分为未知的组集合，并且在每个时间段，每个用户从共同的（但不断变化的）特定于组的分布中提取单个位。我们还提供频率和重要估计的应用程序。
There are now several large scale deployments of differential privacy used to collect statistical information about users. However, these deployments periodically recollect the data and recompute the statistics using algorithms designed for a single use. As a result, these systems do not provide meaningful privacy guarantees over long time scales. Moreover, existing techniques to mitigate this effect do not apply in the “local model” of differential privacy that these systems use. In this paper, we introduce a new technique for local differential privacy that makes it possible to maintain up-to-date statistics over time, with privacy guarantees that degrade only in the number of changes in the underlying distribution rather than the number of collection periods. We use our technique for tracking a changing statistic in the setting where users are partitioned into an unknown collection of groups, and at every time period each user draws a single bit from a common (but changing) group-specific distribution. We also provide an application to frequency and heavy-hitter estimation.