Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (8): 2340-2344.DOI: 10.11772/j.issn.1001-9081.2019122220

• Network and communications • Previous Articles     Next Articles

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

JIN Bo1,2, ZHANG Zhiyong1,2, ZHAO Ting1,2   

  1. 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).

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

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

  1. 1. 河南科技大学 信息工程学院, 河南洛阳 471023;
    2. 河南省网络空间安全应用国际联合实验室(河南科技大学), 河南洛阳 471023
  • 通讯作者: 张志勇(1975-),男,河南新乡人,教授,博士生导师,博士,CCF高级会员,主要研究方向:网络空间安全、大数据、人工智能、可信计算、访问控制;xidianzzy@126.com
  • 作者简介:金波(1992-),男,河南信阳人,硕士研究生,CCF会员,主要研究方向:网络安全、位置隐私保护;赵婷(1995-),女,山西长治人,硕士研究生,CCF会员,主要研究方向:应用密码学、云存储安全。
  • 基金资助:
    国家自然科学基金资助项目(61972133);河南省中原千人计划中原科技创新领军人才项目(204200510021)。

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

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

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

CLC Number: