基于相对熵和K-means的形状相似差分隐私轨迹保护机制

朱素霞; 刘抒伦; 孙广路

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

您当前的位置：

首页 >

文章列表页 >

基于相对熵和K-means的形状相似差分隐私轨迹保护机制

学术论文 | 更新时间：2024-06-05

- 基于相对熵和K-means的形状相似差分隐私轨迹保护机制
- Shape similarity differential privacy trajectory protection mechanism based on relative entropy and K-means
- 通信学报 2021年42卷第2期页码：113-123
- 作者机构：
  
  哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
- 作者简介：
  
  [ "朱素霞（1978- ），女，山东寿光人，博士，哈尔滨理工大学副教授、硕士生导师，主要研究方向为隐私与安全、物联网、并行计算等。" ]
  [ "刘抒伦（1996- ），男，黑龙江哈尔滨人，哈尔滨理工大学硕士生，主要研究方向为差分隐私、轨迹保护。" ]
  [ "孙广路（1979- ），男，黑龙江哈尔滨人，博士，哈尔滨理工大学教授、博士生导师，主要研究方向为计算机网络与信息安全、机器学习、智能信息处理等。" ]
- 基金信息：
  
  国家自然科学青年基金资助项目(61502123);黑龙江省留学归国人员科学基金资助项目(LC2018030)
- DOI：10.11959/j.issn.1000-436x.2021008
  中图分类号： TP391
- 网络出版日期：2021-02，
  
  纸质出版日期：2021-02-25
- 稿件说明：
移动端阅览
朱素霞, 刘抒伦, 孙广路. 基于相对熵和K-means的形状相似差分隐私轨迹保护机制[J]. 通信学报, 2021,42(2):113-123.

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.
朱素霞, 刘抒伦, 孙广路. 基于相对熵和K-means的形状相似差分隐私轨迹保护机制[J]. 通信学报, 2021,42(2):113-123. DOI： 10.11959/j.issn.1000-436x.2021008.

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. DOI： 10.11959/j.issn.1000-436x.2021008.

摘要

为解决绝大多数研究未充分考虑位置对隐私预算的敏感程度以及轨迹形状带来的影响，使发布的轨迹可用性较差的问题，提出了基于相对熵和K-means的形状相似差分隐私轨迹保护机制。首先，根据地理空间的拓扑关系，利用相对熵计算真实位置对隐私预算的敏感程度，设计了位置敏感的隐私级别实时计算算法，并与差分隐私预算结合建立了一个新的隐私模型。其次，通过K-means算法对发布位置进行聚类，得到与真实位置方向最相似的发布位置集合，并引入 Fréchet 距离衡量发布轨迹与真实轨迹的相似性，提升发布轨迹的可用性。通过对真实数据集的实验表明，所提轨迹保护机制与其他方法相比在轨迹可用性方面有明显的优势。

Abstract

To solve the problem that most studies had not fully considered the sensitivity of location to privacy budget and the influence of trajectory shape

which made the usability of published trajectory poor

a shape similarity differential privacy trajectory protection mechanism based on relative entropy and K-means was proposed.Firstly

according to the topological relationship of geographic space

relative entropy was used to calculate the sensitivity of real location to privacy budget

a real-time calculation method of location sensitive privacy level was designed

and a new privacy model was built in combination with differential privacy budget.Secondly

K-means algorithm was used to cluster the release position to obtain the release position set that was most similar to the real position direction

and Fréchet distance was introduced to measure the similarity between the release track and the real track

so as to improve the availability of the release track.Experiments on real data sets show that the proposed trajectory protection mechanism has obvious advantages in trajectory availability compared with others.

关键词

Keywords

references

JUNGLAS I A , WATSON R T . Location-based services [J ] . IEEE Pervasive Computing , 2017 , 9 ( 3 ): 11 - 12 .

DEY A , HIGHTOWER J , LARA E D , et al . Location-based services [J ] . IEEE Pervasive Computing , 2009 , 9 ( 1 ): 11 - 12 .

BERESFORD A R , STAJANO F . Location privacy in pervasive computing [J ] . IEEE Pervasive Computing , 2003 , 2 ( 1 ): 46 - 55 .

ZHAO P , LI J , ZENG F , et al . ILLIA:enabling k-anonymity-based privacy preserving against location injection attacks in continuous LBS queries [J ] . IEEE Internet of Things Journal , 2018 , 5 ( 2 ): 1033 - 1042 .

ENCK W , GILBERT P , HAN S , et al . TaintDroid:an information-flow tracking system for realtime privacy monitoring on smartphones [J ] . ACM Transactions on Computer Systems (TOCS) , 2014 , 32 ( 2 ): 1 - 2 .

PEREZ S . Recently confirmed Myspace hack could be the largest yet [R ] . Tech Crunch ,(2016-05-31)[2020-07-07 ] .

LI L , GOODCHILD M F . Is privacy still an issue in the era of big data? Location disclosure in spatial footprints [C ] // International Conference on Geoinformatics . Piscataway:IEEE Press , 2013 : 1 - 4 .

BHASKARA A , DADUSH D , KRISHNASWAMY R , et al . Unconditional differentially private mechanisms for linear queries [C ] // Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing . New York:ACM Press , 2012 : 1269 - 1284 .

CHATZIKOKOLAKIS K , ANDRÉS M E , BORDENABE N E , et al . Broadening the scope of differential privacy using metrics [C ] // International Symposium on Privacy Enhancing Technologies Symposium . Berlin:Springer , 2013 : 82 - 102 .

王超 , 杨静 , 张健沛 . 基于轨迹位置形状相似性的隐私保护算法 [J ] . 通信学报 , 2015 , 36 ( 2 ): 1 - 14 .

WANG C , YANG J , ZHANG J P . Privacy preserving algorithm based on trajectory location and shape similarity [J ] . Journal on Communications , 2015 , 36 ( 2 ): 1 - 14 .

霍峥 , 孟小峰 . 轨迹隐私保护技术研究 [J ] . 计算机学报 , 2011 , 34 ( 10 ): 1820 - 1830 .

HUO Z , MENG X F . A survey of trajectory privacy preserving techniques [J ] . Chinese Journal of Computers , 2011 , 34 ( 10 ): 1820 - 1830 .

ZHANG S B , MAO X J , CHOO R K , et al . A trajectory privacy-preserving scheme based on a dual-k mechanism for continuous location-based services [J ] . Information Sciences , 2020 , 527 : 406 - 419 .

SHAHAM S , DING M , LIU B , et al . Privacy preserving location data publishing:a machine learning approach [J ] . IEEE Transactions on Knowledge and Data Engineering , 2020 , PP ( 99 ): 1 - 14 .

LAN J , GOU S , GU J , et al . IoT trajectory data privacy protection based on enhanced mix-zone [C ] // 2019 IEEE 3rd Advanced Information Management,Communicates,Electronic and Automation Control Conference . Piscataway:IEEE Press , 2019 : 942 - 946 .

赵婧 , 张渊 , 李兴华 , 等 . 基于轨迹频率抑制的轨迹隐私保护方法 [J ] . 计算机学报 , 2014 , 37 ( 10 ): 2096 - 2106 .

ZHAO J , ZHANG Y , LI X H , et al . A Trajectory privacy protection approach via trajectory frequency suppression [J ] . Chinese Journal of Computers , 2014 , 37 ( 10 ): 2096 - 2106 .

MANO K , MINAMI K , MARUYAMA H . Privacy-preserving publishing of pseudonym-based trajectory location data set [C ] // Eighth International Conference on Availability . Piscataway:IEEE Press , 2013 : 615 - 624 .

PINGLEY A , ZHANG N , FU X , et al . Protection of query privacy for continuous location based services [C ] // INFOCOM IEEE International Conference on Computer Communications . Piscataway:IEEE Press , 2011 : 1710 - 1718 .

DWORK C , KENTHAPADI K , MCSHERRY F , et al . Our data,ourselves:privacy via distributed noise generation [C ] // International Conference on Advances in Cryptology-EUROCRYPT . Saarland:DBLP , 2006 : 486 - 503 .

DWORK C , MCSHERRY F , NISSIM K , et al . Calibrating noise to sensitivity in private data analysis [C ] // Theory of Cryptography Conference . Berlin:Springer , 2006 : 265 - 284 .

高志强 , 王宇涛 . 差分隐私技术研究进展 [J ] . 通信学报 , 2017 , 38 ( Z1 ): 155 - 159 .

GAO Z Q , WANG Y T . Survey on differential privacy and its progress [J ] . Journal on Communications , 2017 , 38 ( Z1 ): 155 - 159 .

李效光 , 李晖 , 李凤华 , 等 . 差分隐私综述 [J ] . 信息安全学报 , 2018 , 39 ( 5 ): 96 - 108 .

LI X G , LI H , LI F H , et al . A survey on differential privacy [J ] . Journal of Cyber Security , 2018 , 39 ( 5 ): 96 - 108 .

叶青青 , 孟小峰 , 朱敏杰 , 等 . 本地化差分隐私研究综述 [J ] . 软件学报 , 2018 , 29 ( 7 ): 1981 - 2005 .

YE Q Q , MENG X F , ZHU M J , et al . Survey on local differential privacy [J ] . Journal of Software , 2018 , 29 ( 7 ): 1981 - 2005 .

CHEN R , FUNG B , 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 Press , 2012 : 213 - 221 .

HUA J , GAO Y , ZHONG S . Differentially private publication of general time-serial trajectory data [C ] // Computer Communications . Piscataway:IEEE Press , 2015 : 549 - 557 .

CHEN R , ACS G , CASTELLUCCIA C . Differentially private sequential data publication via variable-length n-grams [C ] // Proceedings of the 2012 ACM Conference on Computer and Communications Security . New York:ACM Press , 2012 : 638 - 649 .

SHAO D , JIANG K , KISTER T , et al . Publishing trajectory with differential privacy:a posteriori vs.a posteriori sampling mechanisms [C ] // International Conference on Database and Expert Systems Applications . Berlin:Springer , 2013 : 357 - 365 .

JIANG K , SHAO D , STÉPHANE B , et al . Publishing trajectories with differential privacy guarantees [C ] // Proceedings of the 25th International Conference on Scientific and Statistical Database Management . New York:ACM Press , 2013 : 1 - 12 .

HE X , CORMODE G , MACHANAVAJJHALA A , et al . DPT:differentially private trajectory synthesis using hierarchical reference systems [J ] . Proceedings of the VLDB Endowment , 2015 , 8 ( 11 ): 1154 - 1165 .

CHATZIKOKOLAKIS K , PALAMIDESSI C , STRONATI M . Location privacy via geo-indistinguishability [C ] // International Colloquium on Theoretical Aspects of Computing . Berlin:Springer , 2015 : 28 - 38 .

XIAO Y , LI X . Protecting Locations with differential privacy under temporal correlations [C ] // The 22nd ACM SIGSAC Conference . New York:ACM Press , 2015 : 1298 - 1309 .

BORDENABE N E , CHATZIKOKOLAKIS K , PALAMIDESSI C . Optimal geo-indistinguishable mechanisms for location privacy [C ] // Proceedings of the 2014 ACM SIGSAC conference on computer and communications security . New York:ACM Press , 2014 : 251 - 262 .

吴云乘 , 陈红 , 赵素云 , 等 . 一种基于时空相关性的差分隐私轨迹保护机制 [J ] . 计算机学报 , 2018 , 41 ( 2 ): 309 - 321 .

WU Y C , CHEN H , ZHAO S Y , et al . Differentially private trajectory protection based on spatial and temporal correlation [J ] . Chinese Journal of Computers , 2018 , 41 ( 2 ): 309 - 321 .

HU Z , YANG J . Differential privacy protection method based on published trajectory cross-correlation constraint [J ] . PLOS ONE , 2020 , 15 ( 8 ): 1 - 25 .

ZHOU K , WANG J . Trajectory protection scheme based on fog computing and K-anonymity in IoT [C ] // 2019 20th Asia-Pacific Network Operations and Management Symposium (APNOMS) . Piscataway IEEE Press , 2019 : 1 - 6 .

ALT H , GODAU M . Computing the Fréchet distance between two polygonal curves [J ] . International Journal of Computational Geometry＆ Applications , 1995 , 5 ( 1-2 ): 75 - 91 .

TUNHAO Y W P , . Protecting moving trajectories with dummies [C ] // 2007 International Conference on Mobile Data Management . Piscataway:IEEE Press , 2007 : 278 - 282 .

浏览量

446

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

基于预测和滑动窗口的轨迹差分隐私保护机制

基于模糊影响图的差分隐私算法保护效果评估方法

DAGUARD：联邦学习下的分布式后门攻击防御方案

基于目标扰动的AdaBoost算法