基于本地差分隐私的键-值数据精确收集方法

Key-Value Data Accurate Collection under Local Differential Privacy

基于本地差分隐私的键-值数据的收集与分析得到了研究者的广泛关注.键与值的值域大小、二者之间的关联性、报告给收集者的通信方式以及本地扰动机制直接制约着频率与均值估计的精度.针对现有键-值数据本地扰动方法存在的不足,该文提出了一种精确且有效的本地扰动方法LDPKV(Locally Differentially Private Key-Value data collection),该方法结合输入值域与输出值域之间的整体映射关系,在较少通信代价与不分割隐私预算的情况下,对键-值对进行统一处理.其主要思想是:首先对每个用户所拥有的键-值对进行统一离散化处理;结合每个用户的离散化结果,利用伯努利采样技术随机地抽样一条键-值对进行本地随机扰动;然后将扰动后的键-值对报告给收集者.收集者利用每个用户的报告值估计每个键的频率以及所对应值的均值.理论分析了LDPKV方法产生的方差与最大偏差,以及与现有键-值数据收集方法在真实与合成数据集上进行综合比较.实验结果表明LDPKV方法均优于同类方法.

Privacy-preserving data collection is an important problem that has attracted much research attention.The state-of-the-art solution for this problem is local differential privacy,which provides a strong protection by adding random noise from users.Existing methods with local differential privacy,however,rarely focus on key-value data collection.In this paper,given a set U of users,we study locally differentially private algorithms for collecting key-value data over U to estimate the frequency of each key and mean of the value.Existing methods for key-value data collection mostly adopt direct encoding mechanisms and local perturbation mechanisms,which locally encode and perturb the value of each user.The two mechanisms,however,require that we have to transform the whole domain of key-value data and split the privacy budget.The transformation of the whole domain makes the communication cost too high.Furthermore,the partition of the budget leads to excessive noise and lower utility.To remedy the deficiency of existing methods,this paper proposes an accurate and efficient method with local differential privacy,called LDPKV(Locally Differentially Private Key-Value data collection)to collect and analyze key-value data.LDPKV firstly discretes the key-value data of each user in terms of the mapping between input and output domain.Based on the discretization,each user in LDPKV randomly samples a key-value pair by using Bernoulli sampling technology,and runs the local randomized response on the sample and reports the index of sample along with the perturbed value to the collector.After that,the collector in LDPKV accumulates all of the reports from users to estimate the frequency of each key and mean of values.Finally,we conduct theoretical analysis on variance and error bound of LDPKV.Based on two metrics:MSE(Mean Square Error)and RE(Relative Error),three groups of experiments were conducted on real and synthetic datasets(TalkingData,JData,GAUSS,PLAW,and LNR)to evaluate the accuracy of the frequency and the mean generated by from LDPKV,Rappor,KRR,PrivKV,PrivKVM,KVOH,and Harmony.For example,based on JData dataset,we fixε=1.6 to compare the accuracy of the above seven methods.It can be seen from Figure 2(a)that the MSE of LDPKV is 0.002,and 1/6 times that of Rappor and KRR,and 1/2 times that of PrivKV,PrivKVM,and KVOH,respectively.From Figure 2(b),whenεvaries from 0.1 to 3.2,LDPKV achieves a small value of MSE on mean evaluation against Rappor,Harmony,PrivKV,PrivKVM,and KVOH.Besides,based on three synthetic datasets,LDPKV still achieves better accuracy than Rappor,KRR,PrivKV,PrivKVM,KVOH,and Harmony.For instance,from Figure 3 to Figure 5,when varyingεfrom 0.1 to 0.8 and varying top k from top10 to top50,we can see that the RE of six methods decreases gradually.Especially,on fixingε=0.2 and top k=top10,the RE of LDPKV is 1/4 times,1/6 times that of Rappor and KRR on LNR and PLAW,respectively.From the results of the above experimental analysis,we can see that LDPKV is better than its competitors.