基于本地化差分隐私的时序位置发布方案研究

doi:10.12263/DZXB.20210338

摘要/Abstract

摘要：

为了解决基于位置的服务（Location Based Service， LBS）在收集用户位置数据时造成的隐私泄露，提出一种本地化差分隐私位置发布模型. 首先，该模型采用了灵活的位置隐私保护方案（个性化隐私设置），即由用户选择已设定的多种隐私策略或定制隐私策略，在此基础上设计了定制隐私策略位置扰动算法（Customized Privacy policy Location Perturbation algorithm， CPLP）；其次，提出并设计一种基于隐马尔可夫模型的时序关联位置隐私发布算法（Temporal Relational Location Privacy publishing algorithm，TRLP），解决发布时序位置时产生的隐私泄露；最后，在GeoLife数据集和Gowalla数据集上通过对比实验验证了该模型的有效性.

关键词: 差分隐私, 位置服务, 时序数据, 隐私发布, 隐马尔可夫模型

Abstract:

In order to solve the privacy leakage problem in location based service(LBS) when collecting user's location data, we proposed a time-serial location data publication model based on local differential privacy. Firstly, the model adapts a flexible location privacy preservation method, allows users to choose or customize their privacy policy(personalized privacy Settings), based on customized privacy policy, we designed a customized privacy policy location perturbation algorithm(CPLP); Secondly, we proposed and designed temporal relational location privacy publishing algorithm(TRLP) based on hidden Markov model(HMM), which can reduce the privacy leakage when releasing the time-serial location data. Finally, we verified the usability of the algorithm on data sets Geolife and Gowalla.

Key words: differential privacy, location based service, time-series data, privacy releasing, hidden markov model

中图分类号:

TP309.2

康海燕, 冀源蕊. 基于本地化差分隐私的时序位置发布方案研究[J]. 电子学报, 2022, 50(9): 2222-2232.

KANG Hai-yan, JI Yuan-rui. Research on Time-Serial Location Data Publication Based on Local Differential Privacy[J]. Acta Electronica Sinica, 2022, 50(9): 2222-2232.

图/表 8

图1 状态坐标系和地图坐标转化示意图

图2 本地化差分隐私时序位置发布模型

图3 定制隐私策略示意图(a)宽松隐私策略　　　　　　　　　　　　　(b)普通隐私策略　　　　　　　　　　　　　　 (c)严格隐私策略

图4 三种隐私策略粒度示意图(a)PGk9 　　　　　　　　　　　　　　　　　　(b)PGk16　　　　　　　　　　　　　　　　　　(c)PGk25

图5 时序关联位置隐私发布示意图

图6 定制隐私策略粒度对算法可用性影响

图7 时序关联位置隐私发布

图8 TRLP算法与基线算法对比

参考文献 28

1	BAO J, HE T F, RUAN S J, et al. Planning bike lanes based on sharing-bikes' trajectories[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2017: 1377-1386.
2	CAO Y, XIAO Y H, TAKAGI S, et al. PGLP: Customizable and rigorous location privacy through policy graph[C]//European Symposium on Research in Computer Security. Cham: Springer, 2020: 655-676.
3	GEDIK B, LIU L. Protecting location privacy with personalized k-anonymity: Architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2008, 7(1): 1-18.
4	DWORK C, KENTHAPADI K, MCSHERRY F, et al. Our data, ourselves: Privacy via distributed noise generation[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg, Berlin: Springer, 2006: 486-503.
5	康海燕, 朱万祥. 位置服务隐私保护[J]. 山东大学学报 (理学版), 2018, 53(11): 35-50.
	KANG Hai-yan, ZHU Wan-xiang.Privacy preservation for location-based services[J]. Journal of Shandong University(Natural Science), 2018, 53(11):35-50. (in Chinese)
6	冯登国, 张敏, 叶宇桐. 基于差分隐私模型的位置轨迹发布技术研究[J]. 电子与信息学报, 2020, 42(1): 74-88.
	FENG D G, ZHANG M, YE Y T. Research on differentially private trajectory data publishing[J]. Journal of Electronics & Information Technology, 2020, 42(1): 74-88. (in Chinese)
7	郑孝遥, 罗永龙, 汪祥舜, 等. 基于位置服务的分布式差分隐私推荐方法研究[J]. 电子学报, 2021, 49(1): 99-110.
	ZHENG X Y, LUO Y L, WANG X S, et al. Research on location-based distributed differential privacy recommendation method[J]. Acta Electronica Sinica, 2021, 49(1): 99-110. (in Chinese)
8	TAKAGI S, CAO Y, ASANO Y, et al. Geo-graph-indistinguishability: Protecting location privacy for LBS over road networks[C]//IFIP Annual Conference on Data and Applications Security and Privacy. Cham: Springer, 2019: 143-163.
9	CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C]//2012 IEEE 28th International Conference on Data Engineering. Piscataway: IEEE, 2012: 20-31.
10	HAY M, LI C, MIKLAU G, et al. Accurate estimation of the degree distribution of private networks[C]//2009 Ninth IEEE International Conference on Data Mining. Piscataway: IEEE, 2009: 169-178.
11	ZHANG J, XIAO X K, XIE X. PrivTree: A differentially private algorithm for hierarchical decompositions[C]//Proceedings of the 2016 International Conference on Management of Data. New York: ACM, 2016: 155-170.
12	XIE H R, TANIN E, KULIK L, et al. Euler histogram tree: A spatial data structure for aggregate range queries on vehicle trajectories[C]//Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science. New York: ACM, 2014: 18-24.
13	TO H, NGUYEN K, SHAHABI C. Differentially private publication of location entropy[C]//Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2016: 1-10.
14	CHEN R, FUNG B C M, DESAI B C, et al. Differentially private transit data publication: A case study on the Montreal transportation system[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. New York: ACM, 2012: 213-221.
15	霍峥, 孟小峰. 一种满足差分隐私的轨迹数据发布方法[J]. 计算机学报, 2018, 41(2): 400-412.
	HUO Z, MENG X F. A trajectory data publication method under differential privacy[J]. Chinese Journal of Computers, 2018, 41(2): 400-412. (in Chinese)
16	HUA J Y, GAO Y, ZHONG S. Differentially private publication of general time-serial trajectory data[C]//2015 IEEE Conference on Computer Communications. Piscataway: IEEE, 2015: 549-557.
17	ZHAO X D, PI D C, CHEN J F. Novel trajectory privacy-preserving method based on prefix tree using differential privacy[J]. Knowledge-Based Systems, 2020, 198: 105940.
18	杨高明, 朱海明, 方贤进, 等. 局部差分隐私约束的关联属性不变后随机响应扰动[J]. 电子学报, 2019, 47(5): 1079-1085.
	YANG G M, ZHU H M, FANG X J, et al. Invariant post-random response perturbation for correlated attributes under local differential privacy constraint[J]. Acta Electronica Sinica, 2019, 47(5): 1079-1085. (in Chinese)
19	XIONG S J, SARWATE A D, MANDAYAM N B. Randomized requantization with local differential privacy[C]//2016 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway: IEEE, 2016: 2189-2193.
20	SARWATE A D, SANKAR L. A rate-disortion perspective on local differential privacy[C]//2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton). Piscataway: IEEE, 2014: 903-908.
21	WANG T, ZHANG X F, FENG J Y, et al. A comprehensive survey on local differential privacy toward data statistics and analysis[J]. Sensors (Basel, Switzerland), 2020, 20(24): 7030.
22	GARFINKEL S L, ABOWD J M, POWAZEK S. Issues encountered deploying differential privacy[C]//Proceedings of the 2018 Workshop on Privacy in the Electronic Society. New York: ACM, 2018: 133-137.
23	CORMODE G, JHA S, KULKARNI T, et al. Privacy at scale: Local differential privacy in practice[C]//Proceedings of the 2018 International Conference on Management of Data. New York: ACM, 2018: 1655-1658.
24	XIAO Y H, XIONG L. Protecting locations with differential privacy under temporal correlations[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 1298-1309.
25	HARDT M, TALWAR K. On the geometry of differential privacy[C]//Proceedings of the Forty-second ACM Symposium on Theory of Computing. New York: ACM, 2010: 705-714.
26	HE X, MACHANAVAJJHALA A, DING B L. Blowfish privacy: Tuning privacy-utility trade-offs using policies[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York: ACM,2014: 1447-1458.
27	ZHENG Y, XIE X, MA W. GeoLife: A collaborative social networking service among user, location and trajectory.[J]. IEEE Data Eng Bull, 2010, 33(2): 32-39.
28	CHO E, MYERS S A, LESKOVEC J. Friendship and mobility: User movement in location-based social networks[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 1082-1090.

[1]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[2]	张明宇, 王琦, 于洋. 基于LSTM-DHMM的MOSFET器件健康状态识别与故障时间预测[J]. 电子学报, 2022, 50(3): 643-651.
[3]	刘芳, 朱天贺, 苏卫星, 刘阳. 基于高斯隐马尔可夫模型的人机共享控制区域化决策算法[J]. 电子学报, 2022, 50(11): 2659-2667.
[4]	王相海, 宋若曦, 曲思洁, 穆振华, 宋传鸣. 图像多尺度几何分析域隐马尔可夫树模型研究进展[J]. 电子学报, 2022, 50(1): 238-249.
[5]	袁水莲, 皮德常, 胥萌. 基于差分隐私的轨迹隐私保护方法[J]. 电子学报, 2021, 49(7): 1266-1273.
[6]	郑孝遥, 罗永龙, 汪祥舜, 孙丽萍, 陈付龙, 胡桂银, 汪小寒. 基于位置服务的分布式差分隐私推荐方法研究[J]. 电子学报, 2021, 49(1): 99-110.
[7]	陈思, 付安民, 柯海峰, 苏铓, 孙怀江. MCDP:基于神经网络的多集群分布式差分隐私数据发布方法[J]. 电子学报, 2020, 48(12): 2297-2303.
[8]	方晨, 郭渊博, 王娜, 甄帅辉, 唐国栋. 基于生成对抗网络的差分隐私数据发布方法[J]. 电子学报, 2020, 48(10): 1983-1992.
[9]	彭慧丽, 金凯忠, 付聪聪, 付楠, 张啸剑. 基于序列格的隐私时序模式挖掘方法[J]. 电子学报, 2020, 48(1): 153-163.
[10]	杨高明, 朱海明, 方贤进, 苏树智. 局部差分隐私约束的关联属性不变后随机响应扰动[J]. 电子学报, 2019, 47(5): 1079-1085.
[11]	王辛, 王晓峰, 李卫民. 一种求解最小割的警示传播算法[J]. 电子学报, 2019, 47(11): 2386-2391.
[12]	吴宁博, 彭长根, 牟其林. 面向关联属性的差分隐私信息熵度量方法[J]. 电子学报, 2019, 47(11): 2337-2343.
[13]	鲜征征, 李启良, 黄晓宇, 陆寄远, 李磊. 融合显/隐式信任协同过滤算法的差分隐私保护[J]. 电子学报, 2018, 46(12): 3050-3059.
[14]	范利云, 左万利, 王英, 王鑫. 一种基于差分隐私和时序的推荐系统模型研究[J]. 电子学报, 2017, 45(9): 2057-2064.
[15]	叶阿勇, 林少聪, 马建峰, 许力. 一种主动扩散式的位置隐私保护方法[J]. 电子学报, 2015, 43(7): 1362-1368.