满足本地化差分隐私的众包位置数据采集
|
摘要
针对位置数据众包采集中个人位置隐私泄露的问题,提出了一种满足本地化差分隐私的位置数据众包采集方法。首先,使用逐点插入法构造维诺图,对路网空间进行分割;然后,采用满足本地化差分隐私的随机扰动的方式对每个维诺格中的位置数据进行扰动;再次,设计了一种在扰动数据集上进行空间范围查询的方法,获得对真实结果的无偏估计;最后,在空间范围查询下进行了实验验证,并与保护隐私的轨迹数据采集(PTDC)算法进行了对比,算法查询误差率最坏不超过40%,最好情况在20%以下,运行时间在8 s以内,在隐私保护度高于PTDC算法的前提下,上述参数优于PTDC算法。
To solve the problem of privacy leakage in crowdsourced location data collection, a locally differentially private location data collection method with crowdsourcing was proposed. Firstly, a Voronoi diagram constructed by point-by-point insertion method was used to partition the road network space. Secondly, a random disturbance satisfying local differential privacy was used to disturb the original location data in each Voronoi grid. Thirdly, a designed spatial range query method was applied to noisy datasets to get the unbiased estimation of the actual result. Finally, experiments were carried out on spatial range queries to compare the proposed algorithm with PTDC(Privacy-preserving Trajectory Data Collection) algorithm. The results show that the query error rate is no more than 40%, and less than 20%in the best situation, and the running time is less than 8 seconds, which are better than those of PTDC algorithm while the proposed method has a higher degree of privacy preserving.
To solve the problem of privacy leakage in crowdsourced location data collection, a locally differentially private location data collection method with crowdsourcing was proposed. Firstly, a Voronoi diagram constructed by point-by-point insertion method was used to partition the road network space. Secondly, a random disturbance satisfying local differential privacy was used to disturb the original location data in each Voronoi grid. Thirdly, a designed spatial range query method was applied to noisy datasets to get the unbiased estimation of the actual result. Finally, experiments were carried out on spatial range queries to compare the proposed algorithm with PTDC(Privacy-preserving Trajectory Data Collection) algorithm. The results show that the query error rate is no more than 40%, and less than 20%in the best situation, and the running time is less than 8 seconds, which are better than those of PTDC algorithm while the proposed method has a higher degree of privacy preserving.
引文
[1]黄毅,霍峥,孟小峰.CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J].计算机学报,2011,34(10):1976-1985.(HUANG Y,HUO Z,MENG X F.CoPrivacy:a collaborative location privacy-preserving method without cloak region[J].Chinese Journal of Computers,2011,34(10):1976-1985.)
[2]SEI Y,OHSUGA A.An algorithm for privacy-preserving location data collection by probabilistic dummy generation[J].IEEE Transactions on Electronics Information and Systems,2015,135(6):660-670.
[3]ZHANG L,ZHANG W.Generalization-based privacy-preserving data collection[C]//Proceedings of the 2008 International Conference on Data Warehousing and Knowledge Discovery.Berlin:Springer,2008:115-124.
[4]HIGUCHI T,MARTIN P,CHAKRABORTY S,et al.AnonyCast:privacy-preserving location distribution for anonymous crowd tracking systems[C]//UbiComp'15:Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York:ACM,2015:1119-1130.
[5]GIDOFALVI G,HUANG X,PEDERSEN T B.Privacy:preserving trajectory collection[C]//GIS'08:Proceedings of the 16th ACMSIGSPATIAL International Conference on Advances in Geographic Information Systems.New York:ACM,2008:Article No.46.
[6]NGUYEN T T,XIAO X,YANG Y,et al.Collecting and analyzing data from smart device users with local differential privacy[EB/OL].[2018-06-19].https://arxiv.org/pdf/1606.05053.pdf.
[7]QIN Z,YANG Y,YU T,et al.Heavy hitter estimation over set-valued data with local differential privacy[C]//CCS'16:Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.New York:ACM,2016:192-203.
[8]TO H,GHINITA G,SHAHABI C.A framework for protecting worker location privacy in spatial crowdsourcing[J].Proceedings of the VLDB Endowment,2014,7(10):919-930.
[9]CHEN R,LI H,QIN A K,et al.Private spatial data aggregation in the local setting[C]//Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering.Washington DC:IEEEComputer Society,2016:289-300.
[10]DWORK C.Differential privacy[C]//ICALP'06:Proceedings of the 33rd International Conference on Automata,Languages and Programming.Berlin:Springer,2006:1-12.
[11]DWORK C,LEI J.Differential privacy and robust statistics[C]//STOC'09:Proceedings of the 41st Annual ACM Symposium on Theory of Computing.New York:ACM,2009:371-380.
[12]XIONG S,SARWATE A D,MANDAYAM N B.Randomized requantization with local differential privacy[C]//Proceedings of2016 IEEE International Conference on Acoustics.Washington,DC:IEEE Computer Society.2016:2189-2193.
[13]WARNER S L.Randomized response:a survey technique for eliminating evasive answer bias[J].Journal of the American Statistical Association,1965,60(309):63-69.
[14]PAN X,WU L,HU Z,et al.Voronoi-based spatial cloaking algorithm over road network[C]//Proceedings of the 2014 International Conference on Database and Expert Systems Applications.Berlin:Springer,2014:273-280.
[15]霍峥,王卫红,曹玉辉.PTDC:路网环境中感知隐私的轨迹数据采集技术[J].计算机应用,2017:37(9):2567-2571.(HUO Z,WANG W H,CAO Y H.PTDC:privacy-aware trajectory data collection technology under road network constraint[J].Journal of Computer Applications,2017,37(9):2567-2571.)
[2]SEI Y,OHSUGA A.An algorithm for privacy-preserving location data collection by probabilistic dummy generation[J].IEEE Transactions on Electronics Information and Systems,2015,135(6):660-670.
[3]ZHANG L,ZHANG W.Generalization-based privacy-preserving data collection[C]//Proceedings of the 2008 International Conference on Data Warehousing and Knowledge Discovery.Berlin:Springer,2008:115-124.
[4]HIGUCHI T,MARTIN P,CHAKRABORTY S,et al.AnonyCast:privacy-preserving location distribution for anonymous crowd tracking systems[C]//UbiComp'15:Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York:ACM,2015:1119-1130.
[5]GIDOFALVI G,HUANG X,PEDERSEN T B.Privacy:preserving trajectory collection[C]//GIS'08:Proceedings of the 16th ACMSIGSPATIAL International Conference on Advances in Geographic Information Systems.New York:ACM,2008:Article No.46.
[6]NGUYEN T T,XIAO X,YANG Y,et al.Collecting and analyzing data from smart device users with local differential privacy[EB/OL].[2018-06-19].https://arxiv.org/pdf/1606.05053.pdf.
[7]QIN Z,YANG Y,YU T,et al.Heavy hitter estimation over set-valued data with local differential privacy[C]//CCS'16:Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.New York:ACM,2016:192-203.
[8]TO H,GHINITA G,SHAHABI C.A framework for protecting worker location privacy in spatial crowdsourcing[J].Proceedings of the VLDB Endowment,2014,7(10):919-930.
[9]CHEN R,LI H,QIN A K,et al.Private spatial data aggregation in the local setting[C]//Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering.Washington DC:IEEEComputer Society,2016:289-300.
[10]DWORK C.Differential privacy[C]//ICALP'06:Proceedings of the 33rd International Conference on Automata,Languages and Programming.Berlin:Springer,2006:1-12.
[11]DWORK C,LEI J.Differential privacy and robust statistics[C]//STOC'09:Proceedings of the 41st Annual ACM Symposium on Theory of Computing.New York:ACM,2009:371-380.
[12]XIONG S,SARWATE A D,MANDAYAM N B.Randomized requantization with local differential privacy[C]//Proceedings of2016 IEEE International Conference on Acoustics.Washington,DC:IEEE Computer Society.2016:2189-2193.
[13]WARNER S L.Randomized response:a survey technique for eliminating evasive answer bias[J].Journal of the American Statistical Association,1965,60(309):63-69.
[14]PAN X,WU L,HU Z,et al.Voronoi-based spatial cloaking algorithm over road network[C]//Proceedings of the 2014 International Conference on Database and Expert Systems Applications.Berlin:Springer,2014:273-280.
[15]霍峥,王卫红,曹玉辉.PTDC:路网环境中感知隐私的轨迹数据采集技术[J].计算机应用,2017:37(9):2567-2571.(HUO Z,WANG W H,CAO Y H.PTDC:privacy-aware trajectory data collection technology under road network constraint[J].Journal of Computer Applications,2017,37(9):2567-2571.)