论文标题
在当地差异隐私下对发展数据的频率估计
Frequency Estimation of Evolving Data Under Local Differential Privacy
论文作者
论文摘要
收集和分析不断发展的纵向数据已成为一种普遍做法。在此上下文中保护用户隐私的一种可能方法是使用本地差异隐私（LDP）协议，该协议即使在漏洞或数据滥用的情况下，也可以确保所有用户的隐私保护。现有的LDP数据收集协议，例如Google的Rappor和Microsoft的DBITFLIPPM可以对域的纵向私密线性，该域大小K，这对于大型域而言，例如Internet域，这对于大型域而言过高。为了解决这个问题，在本文中，我们引入了一种新的LDP数据收集协议，用于纵向频率监控，名为纵向本地哈希（LOLOHA），并提供正式的隐私保证。此外，我们的协议的隐私 - 实用性权衡仅相对于较小的域尺寸$ 2 \ leq g \ ll k $线性。 Loloha通过本地哈希与双重随机化结合了域减少方法，以最大程度地减少数据更新所产生的隐私泄漏。正如我们的理论分析以及我们的实验评估所证明的那样，Loloha实现了与当前最新协议的竞争力，同时实质上将纵向隐私预算消耗量最小化，最多可通过多达K/G的数量级。
Collecting and analyzing evolving longitudinal data has become a common practice. One possible approach to protect the users' privacy in this context is to use local differential privacy (LDP) protocols, which ensure the privacy protection of all users even in the case of a breach or data misuse. Existing LDP data collection protocols such as Google's RAPPOR and Microsoft's dBitFlipPM can have longitudinal privacy linear to the domain size k, which is excessive for large domains, such as Internet domains. To solve this issue, in this paper we introduce a new LDP data collection protocol for longitudinal frequency monitoring named LOngitudinal LOcal HAshing (LOLOHA) with formal privacy guarantees. In addition, the privacy-utility trade-off of our protocol is only linear with respect to a reduced domain size $2\leq g \ll k$. LOLOHA combines a domain reduction approach via local hashing with double randomization to minimize the privacy leakage incurred by data updates. As demonstrated by our theoretical analysis as well as our experimental evaluation, LOLOHA achieves a utility competitive to current state-of-the-art protocols, while substantially minimizing the longitudinal privacy budget consumption by up to k/g orders of magnitude.
