基于差分隐私的社交网络位置近邻查询方法

doi:10.11772/j.issn.1001-9081.2019122220

计算机应用 ›› 2020, Vol. 40 ›› Issue (8): 2340-2344.DOI: 10.11772/j.issn.1001-9081.2019122220

基于差分隐私的社交网络位置近邻查询方法

金波^1,2, 张志勇^1,2, 赵婷^1,2

1. 河南科技大学信息工程学院, 河南洛阳 471023;
2. 河南省网络空间安全应用国际联合实验室(河南科技大学), 河南洛阳 471023

收稿日期:2020-01-03 修回日期:2020-03-05 出版日期:2020-08-10 发布日期:2020-05-13
通讯作者: 张志勇(1975-),男,河南新乡人,教授,博士生导师,博士,CCF高级会员,主要研究方向:网络空间安全、大数据、人工智能、可信计算、访问控制;xidianzzy@126.com
作者简介:金波(1992-),男,河南信阳人,硕士研究生,CCF会员,主要研究方向:网络安全、位置隐私保护;赵婷(1995-),女,山西长治人,硕士研究生,CCF会员,主要研究方向:应用密码学、云存储安全。
基金资助:
国家自然科学基金资助项目（61972133）；河南省中原千人计划中原科技创新领军人才项目（204200510021）。

Location nearest neighbor query method for social network based on differential privacy

JIN Bo^1,2, ZHANG Zhiyong^1,2, ZHAO Ting^1,2

1. School of Information Engineering, Henan University of Science and Technology, LuoyangHenan 471023, China;
2. Henan International Joint Laboratory of Cyberspace Security Applications(Henan University of Science and Technology), LuoyangHenan 471023, China

Received:2020-01-03 Revised:2020-03-05 Online:2020-08-10 Published:2020-05-13
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61972133), the Project of Leading Talents in Science and Technology Innovation for Central Plains of Thousands of People Plan in Henan Province (204200510021).

摘要/Abstract

摘要： 针对社交网络中近邻位置查询时个人位置隐私泄漏的问题，采用地理不可区分性机制对位置数据添加随机噪声，提出了一种隐私预算分配方法。首先，对空间区域进行网格化分割，根据用户在不同区域的位置访问量来个性化分配隐私预算；然后，为了解决在扰动位置数据集中近邻查询命中率偏低的问题，提出了一种组合增量近邻查询（CINQ）算法，以扩大需求空间的检索范围，并利用组合查询过滤冗余数据。在仿真实验中，与SpaceTwist算法相比，CINQ算法的查询命中率提高了13.7个百分点。实验结果表明，CINQ算法有效解决了因为查询目标的位置扰动所带来的查询命中率偏低问题，适用于社交网络应用中扰动位置的近邻查询。

关键词: 差分隐私, 隐私预算, 近邻查询, 位置隐私, 地理不可区分性

Abstract: Concerning the problem of privacy leak of personal location when querying the nearest neighbor location in social network, a geo-indistinguishability mechanism was used to add random noise to the location data, and a privacy budget allocation method was proposed. First, the spatial regions were divided into grids, and the personalized privacy budget allocation was performed according to the location hits of user in different regions. Then, in order to solve the problem of low hit rate of the neighbor query in the disturbance location dataset, a Combined Incremental Neighbor Query (CINQ) algorithm was proposed to expand the search range of the demand space, and the combination query was used to filter out the redundancy data. Simulation results show that compared with the SpaceTwist algorithm, the CINQ algorithm had the query hit rate increased by 13.7 percentage points. Experimental results verify that the CINQ algorithm effectively solves the problem of low query hit rate caused by the location disturbance of the query target, and it is suitable for neighbor queries for disturbed locations in social network applications.

Key words: differential privacy, privacy budget, nearest neighbor query, location privacy, geo-indistinguishability

中图分类号:

TP393.08

金波, 张志勇, 赵婷. 基于差分隐私的社交网络位置近邻查询方法[J]. 计算机应用, 2020, 40(8): 2340-2344.

JIN Bo, ZHANG Zhiyong, ZHAO Ting. Location nearest neighbor query method for social network based on differential privacy[J]. Journal of Computer Applications, 2020, 40(8): 2340-2344.

参考文献

[1] 万盛,李凤华,牛犇,等. 位置隐私保护技术研究进展[J]. 通信学报, 2016, 37(12):124-141. (WAN S, LI F H, NIU B, et al. Research progress on location privacy-preserving techniques[J]. Journal on Communications, 2016, 37(12):124-141.)
[2] GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial a temporal cloaking[C]//Proceedings of the 2003 International Conference on Mobile Systems, Applications and Services. New York:ACM, 2003:31-42.
[3] CHOW C Y, MOKBEL M, AREF W G. Casper*:query processing for location services without compromising privacy[J]. ACM Transactions on Database Systems, 2009, 34(4):No.24.
[4] BERESFORD A R, STAJANO F. Mix zones:user privacy in location-aware services[C]//Proceedings of the 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops. Piscataway:IEEE, 2004:127-131.
[5] HOH B, GRUTESER M. Protecting location privacy through path confusion[C]//Proceedings of the 1st International Conference on Security and Privacy for Emerging Areas in Communications Networks. Piscataway:IEEE, 2015:194-205.
[6] HONG J I, LANDAY J A. An architecture for privacy-sensitive ubiquitous computing[C]//Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services. New York:ACM, 2004:177-189.
[7] JUNG K,JO S, PARK S. A game theoretic approach for collaborative caching techniques in privacy preserving location-based services[C]//Proceedings of the 2015 International Conference on Big Data and Smart Computing. Washington, DC:IEEE Computer Society, 2015, 1:59-62.
[8] YIU M L, JENSEN C S, HUANG X, et al. SpaceTwist:managing the trade-offs among location privacy, query performance, and query accuracy in mobile services[C]//Proceedings of the 24th International Conference on Data Engineering. Piscataway:IEEE, 2008:366-375.
[9] SUN R, XIANG G, GAO Q, et al. A study of location privacy protection about k interesting points query based on double anchors[C]//Proceedings of the 2018 Ubiquitous Positioning, Indoor Navigation and Location-Based Services. Piscataway:IEEE, 2018:1-7.
[10] ZHOU C, MA C, YANG S, et al. A location privacy preserving method based on sensitive diversity for LBS[C]//Proceedings of the 11th IFIP International Conference on Network and Parallel Computing, LNCS 8707. Berlin:Springer, 2014:409-422.
[11] ANDRÉS M E, BORDENABE N E, CHATZIKOKOLAKIS K, et al. Geo-indistinguishability:differential privacy for location-based systems[C]//Proceedings of the 2013 ACM Conference on Computer and Communications Security. New York:ACM, 2013:901-914.
[12] 罗惠雯,龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用,2020,40(3):760-764. (LUO H W, LONG S G. Location perturbation algorithm based on geo-indistinguishability of user's region of interest[J]. Journal of Computer Applications, 2020, 40(3):760-764.)
[13] DWORK C, KENTHAPADI K, MCSHERRY F, et al. Our data, ourselves:privacy via distributed noise generation[C]//Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 4004. Berlin:Springer, 2006:486-503.
[14] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Theory of Cryptography Conference, LNCS 3876. Berlin:Springer, 2006:265-284.
[15] ZHANG Z, SUN R, ZHAO C, et al. CyVOD:a novel trinity multimedia social network scheme[J]. Multimedia Tools and Applications, 2016, 76(18):18513-18529.

基于差分隐私的社交网络位置近邻查询方法

Location nearest neighbor query method for social network based on differential privacy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[3]	张豪, 朱睿, 宋栿尧, 方鹏, 夏秀峰. 距离-关键字相似度约束的双色反k近邻查询方法[J]. 计算机应用, 2021, 41(6): 1686-1693.
[4]	涂子璇, 刘树波, 熊星星, 赵晶, 蔡朝晖. 可穿戴设备的数值型流数据差分隐私均值发布[J]. 计算机应用, 2020, 40(6): 1692-1697.
[5]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[6]	罗惠雯, 龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用, 2020, 40(3): 760-764.
[7]	李昆明, 王超迁, 倪巍伟, 鲍晓涵. 基于差分隐私的高精度直方图发布方法[J]. 计算机应用, 2020, 40(11): 3242-3248.
[8]	付宇, 王红. 位置隐私保护的虚拟轨迹填充算法[J]. 计算机应用, 2019, 39(8): 2318-2325.
[9]	马方方, 刘树波, 熊星星, 牛晓光. 可穿戴设备数值型敏感数据本地差分隐私保护[J]. 计算机应用, 2019, 39(7): 1985-1990.
[10]	张书旋, 康海燕, 闫涵. 基于Skyline计算的社交网络关系数据隐私保护[J]. 计算机应用, 2019, 39(5): 1394-1399.
[11]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[12]	汪小寒, 韩慧慧, 张泽培, 俞庆英, 郑孝遥. 树索引数据差分隐私预算分配方法[J]. 计算机应用, 2018, 38(7): 1960-1966.
[13]	宁雪莉, 罗永龙, 邢凯, 郑孝遥. 基于地理社交网络的频繁位置隐私保护算法[J]. 计算机应用, 2018, 38(3): 688-692.
[14]	郑孝遥, 陈冬梅, 刘雨晴, 尤浩, 汪祥舜, 孙丽萍. 基于差分隐私保护的谱聚类算法[J]. 计算机应用, 2018, 38(10): 2918-2922.
[15]	王红, 葛丽娜, 王苏青, 王丽颖, 张翼鹏, 梁竣程. 基于OPTICS聚类的差分隐私保护算法的改进[J]. 计算机应用, 2018, 38(1): 73-78.