基于差分隐私的轨迹隐私保护方案

doi:10.11959/j.issn.1000-436x.2021168

通信学报 ›› 2021, Vol. 42 ›› Issue (9): 54-64.doi: 10.11959/j.issn.1000-436x.2021168

基于差分隐私的轨迹隐私保护方案

陈思¹^,², 付安民¹^,³, 苏铓¹, 孙怀江¹

¹ 南京理工大学计算机科学与工程学院，江苏南京 210094
² 南京理工大学后勤服务中心，江苏南京 210094
³ 中国科学院信息工程研究所，北京 100093

修回日期:2021-03-21 出版日期:2021-09-25 发布日期:2021-09-01
作者简介:陈思（1987− ），女，湖北襄阳人，南京理工大学博士生，主要研究方向为大数据、隐私保护等
付安民（1981− ），男，湖北咸宁人，博士，南京理工大学教授，主要研究方向为物联网安全、机器学习与隐私保护等
苏铓（1987− ），女，内蒙古翁牛特旗人，博士，南京理工大学副教授，主要研究方向为云安全、访问控制与权限管理等
孙怀江（1968− ），男，陕西西安人，博士，南京理工大学教授，主要研究方向为神经网络与机器学习等
基金资助:
国家自然科学基金资助项目(62072239);信息安全国家重点实验室开放基金资助项目(2021-MS-07);中央高校基本科研业务费专项资金资助项目(30920021129);中国高等教育学会“高等教育信息化研究”专项课题基金资助项目(2020XXHD06)

Trajectory privacy protection scheme based on differential privacy

Si CHEN¹^,², Anmin FU¹^,³, Mang SU¹, Huaijiang SUN¹

¹ School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
² Logistics Service Center, Nanjing University of Science and Technology, Nanjing 210094, China
³ Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Revised:2021-03-21 Online:2021-09-25 Published:2021-09-01
Supported by:
The National Natural Science Foundation of China(62072239);Open Foundation of the State Key Laboratory of Information Security of China(2021-MS-07);The Fundamental Research Funds for the Central Universities(30920021129);Special Project of “Higher Education Informatization Research” of China Higher Education Association(2020XXHD06)

摘要/Abstract

摘要：

为了解决现有采样机制和数据混淆方法容易导致公开发布的轨迹数据可用性较低和隐私保护不足的问题，提出了一种基于差分隐私的轨迹隐私保护方案。该方案通过建立新的基于时间泛化和空间分割的高效采样模型，并利用k-means聚类算法进行抽样数据处理，同时借助差分隐私保护机制对轨迹数据进行双重扰动，有效解决了具有强大背景知识的攻击者窃取用户隐私的问题。同时，为适应轨迹数据查询范围的误差边界，设计了有效的数据发布预判机制，保证了发布的轨迹数据的精度。仿真结果表明，与现有的轨迹差分隐私保护方法相比，所提方案在处理效率、隐私保护强度和数据可用性等方面具有明显的优势。

关键词: 差分隐私, 轨迹隐私, 数据采样, 指数机制, 数据发布

Abstract:

To solve the problem that the current sampling mechanism and data obfuscation method may raise insufficient data availability and privacy protection, a trajectory privacy protection scheme based on differential privacy was proposed.A new efficient sampling model based on time generalization and spatial segmentation was presented, and a k-means clustering algorithm was designed to process sampling data.By employing the differential privacy mechanism, the trajectory data was disturbed to solve the user privacy leaking problem caused by the attacker with powerful background knowledge.Simultaneously, to respond to the error boundary of the query range of pandemic, an effective prediction mechanism was designed to ensure the availability of released public track data.Simulation results demonstrate that compared with the existing trajectory differential privacy protection methods, the proposed scheme has obvious advantages in terms of processing efficiency, privacy protection intensity, and data availability.

Key words: differential privacy, trajectory privacy, data sampling, exponential mechanism, data publishing

中图分类号:

TP391

陈思, 付安民, 苏铓, 孙怀江. 基于差分隐私的轨迹隐私保护方案[J]. 通信学报, 2021, 42(9): 54-64.

Si CHEN, Anmin FU, Mang SU, Huaijiang SUN. Trajectory privacy protection scheme based on differential privacy[J]. Journal on Communications, 2021, 42(9): 54-64.

图/表 12

表1

系统参数及其含义"

参数	含义
t	时刻
l	簇心节点
T	轨迹
(x_i, y_i)	第i个查询位置坐标值
ln	Laplace噪声
tc	真实轨迹数目
G	分区个数
P	候选分区
D	原始轨迹数据集
DG	位置泛化后的轨迹数据集
$\bar{P}$	k-means分区
nc	加噪之后的轨迹数目

表1

图1

图2

图3

表2

轨迹优化过程"

产生新轨迹数据集	属于该条新轨迹的原始轨迹数据集	真实记录数统计	是否异常
${\tilde{l}}_{11} \to {\tilde{l}}_{21} \to {\tilde{l}}_{31}$	T₂, T₅, T₈	3	否
${\tilde{l}}_{12} \to {\tilde{l}}_{21} \to {\tilde{l}}_{31}$	null	0	是
${\tilde{l}}_{11} \to {\tilde{l}}_{21} \to {\tilde{l}}_{32}$	null	0	是
${\tilde{l}}_{12} \to {\tilde{l}}_{21} \to {\tilde{l}}_{32}$	T₆	1	否
${\tilde{l}}_{11} \to {\tilde{l}}_{22} \to {\tilde{l}}_{31}$	T₇	1	否
${\tilde{l}}_{12} \to {\tilde{l}}_{22} \to {\tilde{l}}_{31}$	T₁	1	否
${\tilde{l}}_{11} \to {\tilde{l}}_{22} \to {\tilde{l}}_{32}$	null	0	是
${\tilde{l}}_{12} \to {\tilde{l}}_{22} \to {\tilde{l}}_{32}$	T₃, T₄	2	否

表2

表3

轨迹发布过程"

产生新轨迹数据集	真实记录数统计(不发布)	Laplace加噪	是否发布
${\tilde{l}}_{11} \to {\tilde{l}}_{21} \to {\tilde{l}}_{31}$	3	3.2	是
${\tilde{l}}_{12} \to {\tilde{l}}_{21} \to {\tilde{l}}_{32}$	1	1.3	是
${\tilde{l}}_{11} \to {\tilde{l}}_{22} \to {\tilde{l}}_{31}$	1	0.7	是
${\tilde{l}}_{12} \to {\tilde{l}}_{22} \to {\tilde{l}}_{31}$	1	0.5	是
${\tilde{l}}_{12} \to {\tilde{l}}_{22} \to {\tilde{l}}_{32}$	2	2.3	是

表3

表4

图4

图5

图6

图7

图8

参考文献 25

[1]	李家印, 郭文忠, 李小燕 ,等. 基于智能交通的隐私保护道路状态实时监测方案[J]. 通信学报, 2020,41(7): 73-83.
	LI J Y , GUO W Z , LI X Y ,et al. Privacy-preserving real-time road conditions monitoring scheme based on intelligent traffic[J]. Journal on Communications, 2020,41(7): 73-83.
[2]	陈思, 付安民, 柯海峰 ,等. MCDP:基于神经网络的多集群分布式差分隐私数据发布方法[J]. 电子学报, 2020,48(12): 2297-2303.
	CHEN S , FU A M , KE H F ,et al. MCDP:multi-cluster differential privacy data publishing method based on neural network[J]. Acta Electronica Sinica, 2020,48(12): 2297-2303.
[3]	ZHOU C Y , FU A M , YU S ,et al. Privacy-preserving federated learning in fog computing[J]. IEEE Internet of Things Journal, 2020,7(11): 10782-10793.
[4]	叶阿勇, 孟玲玉, 赵子文 ,等. 基于预测和滑动窗口的轨迹差分隐私保护机制[J]. 通信学报, 2020,41(4): 123-133.
	YE A Y , MENG L Y , ZHAO Z W ,et al. Trajectory differential privacy protection mechanism based on prediction and sliding window[J]. Journal on Communications, 2020,41(4): 123-133.
[5]	CHEN S , FU A M , SHEN J ,et al. RNN-DP:a new differential privacy scheme base on recurrent neural network for dynamic trajectory privacy protection[J]. Journal of Network and Computer Applications, 2020,168: 102736.
[6]	WU S , WANG X L , WANG S ,et al. K-anonymity for crowdsourcing database[J]. IEEE Transactions on Knowledge and Data Engineering, 2014,26(9): 2207-2221.
[7]	HE X F , JIN R C , DAI H Y . Leveraging spatial diversity for privacy-aware location-based services in mobile networks[J]. IEEE Transactions on Information Forensics and Security, 2018,13(6): 1524-1534.
[8]	王洁, 王春茹, 马建峰 ,等. 基于位置语义和查询概率的假位置选择算法[J]. 通信学报, 2020,41(3): 53-61.
	WANG J , WANG C R , MA J F ,et al. Dummy location selection algorithm based on location semantics and query probability[J]. Journal on Communications, 2020,41(3): 53-61.
[9]	DWORK C , LEI J . Differential privacy and robust statistics[C]// Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York:ACM Press, 2009: 371-380.
[10]	DWORK C , MCSHERRY F , NISSIM K ,et al. Calibrating noise to sensitivity in private data analysis[C]// Conference on Theory of Cryptography. Berlin:Springer, 2006: 265-284.
[11]	KE H F , FU A M , YU S ,et al. AQ-DP:a new differential privacy scheme based on quasi-identifier classifying in big data[C]// 2018 IEEE Global Communications Conference. Piscataway:IEEE Press, 2018: 1-6.
[12]	WANG Y , YANG L , CHEN X Y ,et al. Enhancing social network privacy with accumulated non-zero prior knowledge[J]. Information Sciences, 2018,445/446: 6-21.
[13]	丁红发, 彭长根, 田有亮 ,等. 基于演化博弈的隐私风险自适应访问控制模型[J]. 通信学报, 2019,40(12): 9-20.
	DING H F , PENG C G , TIAN Y L ,et al. Privacy risk adaptive access control model via evolutionary game[J]. Journal on Communications, 2019,40(12): 9-20.
[14]	CHEN R , FUNG B C M , DESAI B C . Differentially private trajectory data publication[J]. arXiv Preprint,arXiv:1112.2020, 2011.
[15]	HE X , CORMODE G , MACHANAVAJJHALA A ,et al. DPT:differentially private trajectory synthesis using hierarchical reference systems[C]// Proceedings of the VLDB Endowment. New York:ACM Press, 2015: 1154-1165.
[16]	CAO Y , YOSHIKAWA M . Differentially private real-time data release over infinite trajectory streams[C]// 2015 16th IEEE International Conference on Mobile Data Management. Piscataway:IEEE Press, 2015: 68-73.
[17]	GURSOY M E , LIU L , TRUEX S ,et al. Utility-aware synthesis of differentially private and attack-resilient location traces[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2018: 196-211.
[18]	DRAKONAKIS K , ILIA P , IOANNIDIS S ,et al. Please forget where I was last summer:the privacy risks of public location (meta)data[C]// Proceedings 2019 Network and Distributed System Security Symposium. VA:Internet Society, 2019: 1-17.
[19]	YANG M M , ZHU T Q , LIANG K T ,et al. A blockchain-based location privacy-preserving crowdsensing system[J]. Future Generation Computer Systems, 2019,94: 408-418.
[20]	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 Press, 2015: 549-557.
[21]	LI M , ZHU L H , ZHANG Z J ,et al. Achieving differential privacy of trajectory data publishing in participatory sensing[J]. Information Sciences, 2017,400/401: 1-13.
[22]	SHAN H M , ZHANG J P , KRUGER U . Learning linear representation of space partitioning trees based on unsupervised kernel dimension reduction[J]. IEEE Transactions on Cybernetics, 2016,46(12): 3427-3438.
[23]	YUAN J , ZHENG Y , XIE X ,et al. Driving with knowledge from the physical world[C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2011: 316-324.
[24]	YUAN J , ZHENG Y , ZHANG C Y ,et al. T-drive:driving directions based on taxi trajectories[C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM Press, 2010: 99-108.
[25]	彭长根, 丁红发, 朱义杰 ,等. 隐私保护的信息熵模型及其度量方法[J]. 软件学报, 2016,27(8): 1891-1903.
	PENG C G , DING H F , ZHU Y J ,et al. Information entropy models and privacy metrics methods for privacy protection[J]. Journal of Software, 2016,27(8): 1891-1903.

算法	时间复杂度	空间复杂度
TPPDP	Ο(n²)	Ο(n)
TSTDA	Ο(n²lbn)	Ο(n)
NGTMA	Ο(n²)	Ο(n)

基于差分隐私的轨迹隐私保护方案

Trajectory privacy protection scheme based on differential privacy

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 25

相关文章 15

Metrics

推荐阅读 0

[1]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[2]	余晟兴, 陈泽凯, 陈钟, 刘西蒙. DAGUARD：联邦学习下的分布式后门攻击防御方案[J]. 通信学报, 2023, 44(5): 110-122.
[3]	张淑芬, 董燕灵, 徐精诚, 王豪石. 基于目标扰动的AdaBoost算法[J]. 通信学报, 2023, 44(2): 198-209.
[4]	汤凌韬, 王迪, 刘盛云. 面向非独立同分布数据的联邦学习数据增强方案[J]. 通信学报, 2023, 44(1): 164-176.
[5]	袁程胜, 郭强, 付章杰. 基于差分隐私的深度伪造指纹检测模型版权保护算法[J]. 通信学报, 2022, 43(9): 181-193.
[6]	王瀚仪, 李效光, 毕文卿, 陈亚虹, 李凤华, 牛犇. 多级本地化差分隐私算法推荐框架[J]. 通信学报, 2022, 43(8): 52-64.
[7]	张勇, 李丹丹, 韩璐, 黄小红. 隐私保护的群体感知数据交易算法[J]. 通信学报, 2022, 43(5): 1-13.
[8]	康海燕, 冀源蕊. 基于本地化差分隐私的联邦学习方法研究[J]. 通信学报, 2022, 43(10): 94-105.
[9]	晏燕, 丛一鸣, Adnan Mahmood, 盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法[J]. 通信学报, 2022, 43(1): 203-216.
[10]	李洪涛, 任晓宇, 王洁, 马建峰. 基于差分隐私的连续位置隐私保护机制[J]. 通信学报, 2021, 42(8): 164-175.
[11]	蔡剑平, 刘西蒙, 熊金波, 应作斌, 吴英杰. 差分隐私下多重一致性约束问题的逼近方法[J]. 通信学报, 2021, 42(6): 107-117.
[12]	朱素霞, 刘抒伦, 孙广路. 基于相对熵和K-means的形状相似差分隐私轨迹保护机制[J]. 通信学报, 2021, 42(2): 113-123.
[13]	刘杨, 李珺, 陈文韵, 彭木根. 面向6G的雾无线接入网内生安全数据共享机制研究[J]. 通信学报, 2021, 42(1): 67-78.
[14]	叶阿勇,孟玲玉,赵子文,刁一晴,张娇美. 基于预测和滑动窗口的轨迹差分隐私保护机制[J]. 通信学报, 2020, 41(4): 123-133.
[15]	周异辉,鲁来凤,吴振强. 随机响应机制效用优化研究[J]. 通信学报, 2019, 40(6): 74-81.