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

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 12

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

产生新轨迹数据集	属于该条新轨迹的原始轨迹数据集	真实记录数统计	是否异常
${\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	否

产生新轨迹数据集	真实记录数统计(不发布)	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	是

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

Trajectory privacy protection scheme based on differential privacy

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 25

Related Articles 15

Metrics

Recommended 0

[1]	Tao FENG, Liqiu CHEN, Junli FANG, Jianming SHI. Blockchain data sharing scheme based on localized difference privacy and attribute-based searchable encryption [J]. Journal on Communications, 2023, 44(5): 224-233.
[2]	Shengxing YU, Zekai CHEN, Zhong CHEN, Ximeng LIU. DAGUARD: distributed backdoor attack defense scheme under federated learning [J]. Journal on Communications, 2023, 44(5): 110-122.
[3]	Shufen ZHANG, Yanling DONG, Jingcheng XU, Haoshi WANG. AdaBoost algorithm based on target perturbation [J]. Journal on Communications, 2023, 44(2): 198-209.
[4]	Lingtao TANG, Di WANG, Shengyun LIU. Data augmentation scheme for federated learning with non-IID data [J]. Journal on Communications, 2023, 44(1): 164-176.
[5]	Chengsheng YUAN, Qiang GUO, Zhangjie FU. Copyright protection algorithm based on differential privacy deep fake fingerprint detection model [J]. Journal on Communications, 2022, 43(9): 181-193.
[6]	Hanyi WANG, Xiaoguang LI, Wenqing BI, Yahong CHEN, Fenghua LI, Ben NIU. Multi-level local differential privacy algorithm recommendation framework [J]. Journal on Communications, 2022, 43(8): 52-64.
[7]	Yong ZHANG, Dandan LI, Lu HAN, Xiaohong HUANG. Privacy-protected crowd-sensed data trading algorithm [J]. Journal on Communications, 2022, 43(5): 1-13.
[8]	Haiyan KANG, Yuanrui JI. Research on federated learning approach based on local differential privacy [J]. Journal on Communications, 2022, 43(10): 94-105.
[9]	Yan YAN, Yiming CONG, Mahmood Adnan, Quanzheng SHENG. Statistics release and privacy protection method of location big data based on deep learning [J]. Journal on Communications, 2022, 43(1): 203-216.
[10]	Hongtao LI, Xiaoyu REN, Jie WANG, Jianfeng MA. Continuous location privacy protection mechanism based on differential privacy [J]. Journal on Communications, 2021, 42(8): 164-175.
[11]	Jianping CAI, Ximeng LIU, Jinbo XIONG, Zuobin YING, Yingjie WU. Approximation method of multiple consistency constraint under differential privacy [J]. Journal on Communications, 2021, 42(6): 107-117.
[12]	Suxia ZHU, Shulun LIU, Guanglu SUN. Shape similarity differential privacy trajectory protection mechanism based on relative entropy and K-means [J]. Journal on Communications, 2021, 42(2): 113-123.
[13]	Yang LIU, Jun LI, Wenyun CHEN, Mugen PENG. Research on endogenous security data sharing mechanism of F-RAN for 6G [J]. Journal on Communications, 2021, 42(1): 67-78.
[14]	Ayong YE,Lingyu MENG,Ziwen ZHAO,Yiqing DIAO,Jiaomei ZHANG. Trajectory differential privacy protection mechanism based on prediction and sliding window [J]. Journal on Communications, 2020, 41(4): 123-133.
[15]	ZHOU Yihui,LU Laifeng,WU Zhenqiang. Study on utility optimization for randomized response mechanism [J]. Journal on Communications, 2019, 40(6): 74-81.