Locally Differentially Private Frequency Estimation with Consistency
Locally Differentially Private Frequency Estimation with Consistency
复制标题
DOI：
10.14722/ndss.2020.24157
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Tianhao Wang;Milan Lopuhaä-Zwakenberg;Zitao Li;B. Škorić;Ninghui Li
中科院分区：
文献类型：
--
作者：
Tianhao Wang;Milan Lopuhaä-Zwakenberg;Zitao Li;B. Škorić;Ninghui Li
当地差异隐私（LDP）保护用户隐私免受数据收集器的影响。 LDP协议越来越多地部署在该行业中。基本的构建块是频率Oracle（FO）协议，该协议估计值的频率。尽管已经提出了几种FO协议，但设计目标并没有带来回答许多查询的最佳结果。在本文中，我们表明，通过利用所有单个频率都不应为非负数的知识，将后处理步骤添加到FO协议中，它们总计可以使多种任务的准确性明显更好，包括频率，包括个体值，最频繁值的频率以及值子集的频率。我们考虑10种不同利用这些知识的不同方法。我们建立了其中一些之间的理论关系，并进行了广泛的实验评估，以了解应将哪些方法用于不同的查询任务。
Local Differential Privacy (LDP) protects user privacy from the data collector. LDP protocols have been increasingly deployed in the industry. A basic building block is frequency oracle (FO) protocols, which estimate frequencies of values. While several FO protocols have been proposed, the design goal does not lead to optimal results for answering many queries. In this paper, we show that adding post-processing steps to FO protocols by exploiting the knowledge that all individual frequencies should be non-negative and they sum up to one can lead to significantly better accuracy for a wide range of tasks, including frequencies of individual values, frequencies of the most frequent values, and frequencies of subsets of values. We consider 10 different methods that exploit this knowledge differently. We establish theoretical relationships between some of them and conducted extensive experimental evaluations to understand which methods should be used for different query tasks.