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 have longitudinal privacy linear to the domain size k, which can be 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<=g<<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.
翻译:收集并分析不断演变的纵向数据已成为一种常见做法。在这种情况下,保护用户隐私的一种可能做法是使用地方差异隐私协议(LDP),确保即使在违反或滥用数据的情况下也保护所有用户的隐私。现有的LDP数据收集协议(如谷歌的RAPPOR和微软的dBitFlippM)将长视隐私线线线直通于K范围,这对因特网域等大域而言可能过于过分。为了解决这个问题,我们在本文件中为长视频率监测引入了新的LOnggal Local Hashing(LOLOHA)数据收集协议(LOLOHA),并附有正式的隐私保障。此外,我们的协议的隐私使用权交易只是线性交易,仅涉及缩小域号2 ⁇ g ⁇ k。 LOLOHA将区域削减方法与双随机化结合起来,以尽量减少数据更新引起的隐私泄漏。正如我们的理论分析以及我们的实验性评估所证明的那样,LOLOHA实现了对当前状态协议的实用性竞争,同时将长期隐私预算订单从K/消费到kg水平。