高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于差分隐私模型的位置轨迹发布技术研究

冯登国 张敏 叶宇桐

冯登国, 张敏, 叶宇桐. 基于差分隐私模型的位置轨迹发布技术研究[J]. 电子与信息学报, 2020, 42(1): 74-88. doi: 10.11999/JEIT190632
引用本文: 冯登国, 张敏, 叶宇桐. 基于差分隐私模型的位置轨迹发布技术研究[J]. 电子与信息学报, 2020, 42(1): 74-88. doi: 10.11999/JEIT190632
Dengguo FENG, Min ZHANG, Yutong YE. Research on Differentially Private Trajectory Data Publishing[J]. Journal of Electronics and Information Technology, 2020, 42(1): 74-88. doi: 10.11999/JEIT190632
Citation: Dengguo FENG, Min ZHANG, Yutong YE. Research on Differentially Private Trajectory Data Publishing[J]. Journal of Electronics and Information Technology, 2020, 42(1): 74-88. doi: 10.11999/JEIT190632

基于差分隐私模型的位置轨迹发布技术研究

doi: 10.11999/JEIT190632
基金项目: 国家自然科学基金(U1636216)
详细信息
    作者简介:

    冯登国:男,1965年生,中国科学院院士,研究员,研究方向为网络与信息安全

    张敏:女,1975年生,研究员,研究方向为数据安全与隐私保护

    叶宇桐:男,1993年生,博士生,研究方向为差分隐私保护技术

    通讯作者:

    冯登国 feng@is.iscas.ac.cn

  • 1) 在表2中的时间复杂度分析中,n表示轨迹或位置数据集合的样本数目,m表示轨迹平均长度。
  • 中图分类号: TN918

Research on Differentially Private Trajectory Data Publishing

Funds: The National Natural Science Foundation of China (U1636216)
  • 摘要: 位置轨迹大数据的安全分享、发布需求离不开位置轨迹隐私保护技术支持。在差分隐私出现之前,K-匿名及其衍生模型为位置轨迹隐私保护提供了一种量化评估的手段,但其安全性严重依赖于攻击者所掌握的背景知识,当有新的攻击出现时模型无法提供完善的隐私保护。差分隐私技术的出现有效地弥补了上述问题,越来越多地应用于轨迹数据隐私发布领域中。该文对基于差分隐私理论的轨迹隐私保护技术进行了研究与分析,重点介绍了差分隐私模型下位置直方图、轨迹直方图等空间统计数据发布方法,差分隐私模型下轨迹数据集发布方法,以及连续轨迹实时发布隐私保护模型。与此同时,在对现有方法对比分析的基础上,提出了未来的重点发展方向。
    注释:
    1)  1) 在表2中的时间复杂度分析中,n表示轨迹或位置数据集合的样本数目,m表示轨迹平均长度。
  • 图  1  基于四叉树的差分隐私位置计数查询方法

    图  2  EH模型功能示意图

    图  3  轨迹序列的前缀树表示

    图  4  基于N-gram的搜索树方法

    图  5  轨迹片段在RS2前缀树中的表达示例

    图  6  轨迹聚类方法过程示意图

    表  1  轨迹序列数据集

    序号路径
    1L1→L2→L3
    2L1→L2
    3L3→L2→L1
    4L1→L2→L4
    5L1→L2→L3
    6L3→L2
    7L1→L2→L4→L1
    8L3→L1
    下载: 导出CSV

    表  2  基于差分隐私保护的轨迹信息发布方法比较

    类型数据发布方法隐私保护模型隐私保护机制发布数据类型时间复杂度分析
    空间
    直方图
    四叉索引树,KD-索引树,K叉平均树,PrivTree$ \left( {\varepsilon ,\delta } \right) - {\rm{DP}}$Laplace机制位置直方图噪音的全局敏感度和树高相关,构建四叉树结构的复杂度为O(n·lgn)
    EH-DP, privSHε-DP ε-DPLaplace机制和指数机制轨迹直方图构建EH数据结构的复杂度为O (mn)
    位置熵(LE)$ \left( {\varepsilon ,\delta } \right) - {\rm{DP}}$Laplace机制位置熵直方图用到了平滑敏感度替代全局敏感度,添加噪音较少,计算所有地理位置的熵需要遍历用户的地理位置,复杂度为O(mn)
    轨迹
    集合
    发布
    前缀树,n-gram, DPT, PSTε-DPLaplace机制移动轨迹数据集构建前缀树的复杂度为O(mn·lgm)
    K-means聚类,OPT K-means聚类ε-DPLaplace机制和指数机制移动轨迹数据集若聚类为k,迭代次数平均为t,由于采用差分隐私指数机制,复杂度为O (mktnk)
    连续
    轨迹
    发布
    δ-位置集合,(δ, r)-位置集合ε-DPLaplace机制单个轨迹点假设攻击者知道用户的移动模式,使噪音添加的更合理。时间复杂为O(m|$\Delta $X|) (其中|$\Delta $X|为构建位置集合大小)
    Wasserstein机制,MQM机制,FGS-PufferFish机制ε-PufferFish隐私Laplace机制单条轨迹时间复杂度为O (nkm2·lgm) (其中k为PufferFish定义的空间关联的最大区域)
    下载: 导出CSV
  • [1] BAO Jie, HE Tianfu, RUAN Sijie, et al. Planning bike lanes based on sharing-bikes’ trajectories[C]. The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, Canada, 2017: 1377–1386.
    [2] YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al. T-drive: Driving directions based on taxi trajectories[C]. The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Jose, USA, 2010: 99–108.
    [3] TOCKAR A. Riding with the stars: Passenger privacy in the NYC Taxicab dataset[EB/OL]. https://research.neustar.biz/author/atockar/, 2018.
    [4] W-Pwn. 健身APP泄露军事机密, 包括中国南海[EB/OL]. https://zhuanlan.zhihu.com/p/33405626, 2018.
    [5] CHEN Zhenyu, FU Yanyan, ZHANG Min, et al. The de-anonymization method based on user spatio-temporal mobility trace[C]. The 19th International Conference on Information and Communications Security, Beijing, China, 2017: 459–471.
    [6] ABUL O, BONCHI F, and NANNI M. Never walk alone: Uncertainty for anonymity in moving objects databases[C]. The 24th IEEE International Conference on Data Engineering, Cancun, Mexico, 2008: 376–385.
    [7] TERROVITIS M, POULIS G, MAMOULIS N, et al. Local suppression and splitting techniques for privacy preserving publication of trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(7): 1466–1479. doi:  10.1109/TKDE.2017.2675420
    [8] YAO Lin, WANG Xinyu, WANG Xin, et al. Publishing sensitive trajectory data under enhanced l-diversity model[C]. The 20th IEEE International Conference on Mobile Data Management, Hong Kong, China, 2019: 160–169.
    [9] 冯登国. 大数据安全与隐私保护[M]. 北京: 清华大学出版社, 2018: 194–219.
    [10] DWORK C. Differential privacy[C]. The 33rd International Colloquium on Automata, Languages and Programming, Venice, Italy, 2006: 1–12. doi: 10.1007/11787006_1.
    [11] ZHU Tianqing, LI Gang, ZHOU Wanlei, et al. Differentially private data publishing and analysis: A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(8): 1619–1638. doi:  10.1109/TKDE.2017.2697856
    [12] MCSHERRY F and TALWAR K. Mechanism design via differential privacy[C]. The 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, USA, 2007: 94–103.
    [13] MCSHERRY F D. Privacy integrated queries: An extensible platform for privacy-preserving data analysis[C]. The 2009 ACM SIGMOD International Conference on Management of Data, Rhode Island, USA, 2009: 19–30.
    [14] DWORK C, KENTHAPADI K, MCSHERRY F, et al. Our data, ourselves: Privacy via distributed noise generation[C]. The 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Peterbury, Russia, 2006: 486–503.
    [15] KIFER D and MACHANAVAJJHALA A. No free lunch in data privacy[C]. The 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece, 2011: 193–204.
    [16] GEHRKE J, LUI E, and PASS R. Towards privacy for social networks: A zero-knowledge based definition of privacy[C]. The 8th Conference on Theory of Cryptography, Providence, USA, 2011: 432–449.
    [17] KIFER D and MACHANAVAJJHALA A. Pufferfish: A framework for mathematical privacy definitions[J]. ACM Transactions on Database Systems, 2014, 39(1): Article No.3. doi:  10.1145/2514689
    [18] DWORK C. A firm foundation for private data analysis[J]. Communications of the ACM, 2011, 54(1): 86–95. doi:  10.1145/1866739.1866758
    [19] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]. The 3rd Theory of Cryptography Conference, New York, USA, 2006: 265–284.
    [20] QARDAJI W, YANG Weining, and LI Ninghui. Differentially private grids for geospatial data[C]. The 29th IEEE International Conference on Data Engineering, Brisbane, Australia, 2013: 757–768.
    [21] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C]. The 28th IEEE International Conference on Data Engineering, Washington, USA, 2012: 20–31.
    [22] ZHANG Jun, XIAO Xiaokui, and XIE Xing. PrivTree: A differentially private algorithm for hierarchical decompositions[C]. The 2016 International Conference on Management of Data, San Francisco, USA, 2016: 155–170.
    [23] HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 1021–1032.
    [24] XIAO Yonghui, XIONG Li, and YUAN Chun. Differentially private data release through multidimensional partitioning[C]. The 7th Workshop on Secure Data Management, Singapore, 2010: 150–168.
    [25] XIE Hairuo, TANIN E, and KULIK L. Distributed histograms for processing aggregate data from moving objects[C]. 2007 International Conference on Mobile Data Management, Mannheim, Germany, 2007: 152–157.
    [26] XIE Hairuo, TANIN E, KULIK L, et al. Euler histogram tree: A spatial data structure for aggregate range queries on vehicle trajectories[C]. The 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Dallas/Fort Worth, USA, 2014: 18–24.
    [27] GHANE S, KULIK L, and RAMAMOHANARAO K. Publishing spatial histograms under differential privacy[C]. The 30th International Conference on Scientific and Statistical Database Management, Bozen-Bolzano, Italy, 2018: Article No.14.
    [28] HARDT M, LIGETT K, and MCSHERRY F. A simple and practical algorithm for differentially private data release[C]. Advances in Neural Information Processing Systems, Lake Tahoe, USA, 2012: 2339–2347.
    [29] TO H, NGUYEN K, and SHAHABI C. Differentially private publication of location entropy[C]. The 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Burlingame, USA, 2016: Article No. 35.
    [30] CHEN Rui, FUNG B C M, DESAI B C, et al. Differentially private transit data publication: A case study on the montreal transportation system[C]. The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, 2012: 213–221.
    [31] CHEN Rui, ACS G, and CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams[C]. The 2012 ACM Conference on Computer and Communications Security, Raleigh, USA, 2012: 638–649.
    [32] HE Xi, CORMODE G, MACHANAVAJJHALA A, et al. DPT: Differentially private trajectory synthesis using hierarchical reference systems[J]. The VLDB Endowment, 2015, 8(11): 1154–1165. doi:  10.14778/2809974.2809978
    [33] HE Xi, RAVAL N, and MACHANAVAJJHALA A. A demonstration of VisDPT: Visual exploration of differentially private trajectories[J]. The VLDB Endowment, 2016, 9(13): 1489–1492. doi:  10.14778/3007263.3007291
    [34] HUA Jingyu, GAO Yue, and ZHONG Sheng. Differentially private publication of general time-serial trajectory data[C]. 2015 IEEE Conference on Computer Communications, Hong Kong, China, 2015: 549–557. doi: 10.1109/INFOCOM.2015.7218422.
    [35] LI Meng, ZHU Liehuang, ZHANG ZIjian, et al. Achieving differential privacy of trajectory data publishing in participatory sensing[J]. Information Sciences, 2017, 400/401: 1–13. doi:  10.1016/j.ins.2017.03.015
    [36] ERLINGSSON Ú, PIHUR V, and KOROLOVA A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C]. The 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, USA, 2014: 1054–1067.
    [37] BASSILY R and SMITH A. Local, private, efficient protocols for succinct histograms[C]. The 47th Annual ACM Symposium on Theory of Computing, Portland, USA, 2015: 127–135.
    [38] XIAO Yonghui and XIONG Li. Protecting locations with differential privacy under temporal correlations[C]. The 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, USA, 2015: 1298–1309.
    [39] WANG Shuo, SINNOTT R, and NEPAL S. Protecting the location privacy of mobile social media users[C]. IEEE International Conference on Big Data, Washington, USA, 2016: 1143–1150.
    [40] HARDT M and TALWAR K. On the geometry of differential privacy[C]. The 42nd ACM Symposium on Theory of Computing, Cambridge, UK, 2010: 705–714.
    [41] SONG Shuang, WANG Yizhen, and CHAUDHURI K. Pufferfish privacy mechanisms for correlated data[C]. The 2017 ACM International Conference on Management of Data, Chicago, USA, 2017: 1291–1306.
    [42] OU Lu, QIN Zheng, LIAO Shaolin, et al. An optimal pufferfish privacy mechanism for temporally correlated trajectories[J]. IEEE Access, 2018, 6: 37150–37165. doi:  10.1109/ACCESS.2018.2847720
    [43] DWORK C and ROTH A. The algorithmic foundations of differential privacy[J]. Foundations and Trends® in Theoretical Computer Science, 2014, 9(3/4): 211–407. doi:  10.1561/0400000042
    [44] KELLARIS G, PAPADOPOULOS S, XIAO Xiaokui, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1155–1166. doi:  10.14778/2732977.2732989
    [45] ABADI M, CHU A, GOODFELLOW I, et al. Deep learning with differential privacy[C]. The 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 2016: 308–318.
    [46] GAO Qiang, ZHOU Fan, ZHANG Kunpeng, et al. Identifying human mobility via trajectory embeddings[C]. The 26th International Joint Conference on Artificial Intelligence, Macao, China, 2017: 1689–1695.
    [47] WANG Guowei, LIAO Dongliang, and LI Jing. Complete user mobility via user and trajectory embeddings[J]. IEEE Access, 2018, 6: 72125–72136. doi:  10.1109/ACCESS.2018.2881457
    [48] ZHOU Fan, GAO Qiang, TRAJCEVSKI G, et al. Trajectory-user linking via variational autoencoder[C]. The 27th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018: 3212–3218.
    [49] LI Xiucheng, ZHAO Kaiqi, CONG Gao, et al. Deep representation learning for trajectory similarity computation[C]. The 34th IEEE International Conference on Data Engineering, Paris, France, 2018: 617–628.
    [50] JORGENSEN Z, YU Ting, and CORMODE G. Conservative or liberal? Personalized differential privacy[C]. The 31st IEEE International Conference on Data Engineering, Seoul, South Korea, 2015: 1023–1034.
    [51] LI Haoran, XIONG Li, JI Zhanglong, et al. Partitioning-based mechanisms under personalized differential privacy[C]. The 21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, Jeju, South Korea, 2017: 615–627.
    [52] YE Yutong, ZHANG Min, FENG Dengguo, et al. Multiple privacy regimes mechanism for local differential privacy[C]. The 24th International Conference on Database Systems for Advanced Applications, Chiang Mai, Thailand, 2019: 247–263.
    [53] CHEN Rui, LI Haoran, QIN A K, et al. Private spatial data aggregation in the local setting[C]. The 32nd IEEE International Conference on Data Engineering, Helsinki, Finland, 2016: 289–300.
  • [1] 李攀攀, 谢正霞, 周志刚, 乐光学, 郑仕链, 杨小牛.  基于Hilbert填充曲线的海洋无线传感网源节点位置隐私保护方法, 电子与信息学报. doi: 10.11999/JEIT190364
    [2] 李旻, 何婷婷.  基于随机数三角阵映射的高维大数据二分聚类初始中心高效鲁棒生成算法, 电子与信息学报. doi: 10.11999/JEIT200043
    [3] 杨亚涛, 赵阳, 张卷美, 黄洁润, 高原.  同态密码理论与应用进展, 电子与信息学报. doi: 10.11999/JEIT191019
    [4] 赵星, 彭建华, 游伟.  基于Lyapunov优化的隐私感知计算卸载方法, 电子与信息学报. doi: 10.11999/JEIT190170
    [5] 赵星, 彭建华, 游伟, 陈璐.  基于k-匿名的隐私保护计算卸载方法, 电子与信息学报. doi: 10.11999/JEIT191046
    [6] 方维维, 刘梦然, 王云鹏, 李阳阳, 安竹林.  面向物联网隐私数据分析的分布式弹性网络回归学习算法, 电子与信息学报. doi: 10.11999/JEIT190739
    [7] 邵振峰, 蔡家骏, 王中元, 马照亭.  面向智能监控摄像头的监控视频大数据分析处理, 电子与信息学报. doi: 10.11999/JEIT160712
    [8] 朱小玉, 刘琴, 王国军.  云存储中一种支持可验证的模糊查询加密方案, 电子与信息学报. doi: 10.11999/JEIT160971
    [9] 屠袁飞, 杨庚, 袁冯杰.  脑机接口技术中安全高效的属性基访问控制, 电子与信息学报. doi: 10.11999/JEIT161362
    [10] 移动社交网络中基于代理转发机制的轨迹隐私保护方法, 电子与信息学报. doi: 10.11999/JEIT151136
    [11] 石乐义, 贾聪, 宫剑, 刘昕, 陈鸿龙.  基于共享秘密的伪随机散列函数RFID双向认证协议, 电子与信息学报. doi: 10.11999/JEIT150653
    [12] 张少波, 刘琴, 王国军.  基于网格标识匹配的位置隐私保护方法, 电子与信息学报. doi: 10.11999/JEIT160350
    [13] 陈爱国, 王士同.  具有隐私保护功能的知识迁移聚类算法, 电子与信息学报. doi: 10.11999/JEIT150645
    [14] 罗恩韬, 王国军.  移动社交网络中一种朋友发现的隐私安全保护策略, 电子与信息学报. doi: 10.11999/JEIT151479
    [15] 罗恩韬, 王国军.  大数据中一种基于语义特征阈值的层次聚类方法, 电子与信息学报. doi: 10.11999/JEIT150422
    [16] 葛国栋, 郭云飞, 刘彩霞, 兰巨龙.  内容中心网络中面向隐私保护的协作缓存策略, 电子与信息学报. doi: 10.11999/JEIT140874
    [17] 杨立君, 丁超, 吴蒙.  一种同时保障隐私性与完整性的无线传感器网络可恢复数据聚合方案, 电子与信息学报. doi: 10.11999/JEIT150208
    [18] 戴华, 秦小麟, 刘亮, 季一木, 付雄, 孙研.  基于Z-O编码的两层WSNs隐私保护最值查询处理协议, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00940
    [19] 彭志宇, 李善平.  移动环境下LBS位置隐私保护, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01050
    [20] 李洁, 高新波, 焦李成.  一种基于GA的混合属性特征大数据集聚类算法, 电子与信息学报.
  • 加载中
  • 图(6) / 表ll (2)
    计量
    • 文章访问数:  4458
    • HTML全文浏览量:  834
    • PDF下载量:  85
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-08-26
    • 修回日期:  2019-11-30
    • 网络出版日期:  2019-12-05
    • 刊出日期:  2020-01-21

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注