Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm

Saite CHEN; Weihai LI; Yuanzhi YAO; Nenghai YU

doi:10.11959/j.issn.2096-109x.2023038

您当前的位置：

首页 >

文章列表页 >

Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm

Papers | 更新时间：2024-06-03

- Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm
- Chinese Journal of Network and Information Security Vol. 9, Issue 3, Pages: 60-72(2023)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2023038
  CLC： TP391
- Online First：2023-06，
  
  Published：25 June 2023
- 稿件说明：
移动端阅览
Saite CHEN, Weihai LI, Yuanzhi YAO, et al. Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm[J]. Chinese Journal of Network and Information Security, 2023, 9(3): 60-72.
DOI：

Saite CHEN, Weihai LI, Yuanzhi YAO, et al. Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm[J]. Chinese Journal of Network and Information Security, 2023, 9(3): 60-72. DOI： 10.11959/j.issn.2096-109x.2023038.

摘要

基于位置的服务为人们生活带来便利的同时可能暴露用户的位置隐私。在k近邻查询问题中，构造K匿名区来保护用户位置隐私的方法具有一定的安全性，但会带来较大的通信开销。SpaceTwist方案使用锚点代替真实位置进行k近邻查询，实现简单且通信开销小，不过其无法保证K匿名安全，也没有给出锚点的具体选取方法。为克服SpaceTwist的缺点，一些方案通过引入可信匿名服务器或者使用用户协作的方式计算用户的K匿名组，进而加强算法的查询结束条件以实现K匿名安全；一些方案结合地图中兴趣点的大致分布，提出锚点的优选方法，进一步减小了平均通信开销。基于完善SpaceTwist的考虑，提出轻量级K匿名增量近邻（LKINN，lightweight K-anonymity incremental nearest neighbor）查询位置隐私保护算法，借助凸包这一数学工具计算K匿名组的关键点集合，并在此基础上给出一种锚点的选择方法，能够以更低的响应时间和通信代价实现 K 匿名安全。此外，LKINN 基于混合式位置隐私保护架构，对系统中的所有成员都只做半可信的安全性假设，与现有的一些研究成果相比，降低了安全性假设要求。仿真实验结果表明，LKINN能够防止半可信用户对正常用户位置隐私的窃取，保护地图中正常用户的位置隐私，并且与一些现有方案相比，LKINN拥有更短的查询响应时间以及更小的通信开销。

Abstract

The use of location-based service brings convenience to people’s daily lives

but it also raises concerns about users’ location privacy.In the k-nearest neighbor query problem

constructing K-anonymizing spatial regions is a method used to protects users’ location privacy

but it results in a large waste of communication overhead.The SpaceTwist scheme is an alternative method that uses an anchor point instead of the real location to complete the k-nearest neighbor query

which is simple to implement and has less waste of communication overhead.However

it cannot guarantee K-anonymous security

and the specific selection method of the anchor point is not provided.To address these shortcomings in SpaceTwist

some schemes calculate the user’s K-anonymity group by introducing a trusted anonymous server or using the way of user collaboration

and then enhance the end condition of the query algorithm to achieve K-anonymity security.Other schemes propose the anchor point optimization method based on the approximate distribution of interest points

which can further reduce the average communication overhead.A lightweight K-anonymity incremental nearest neighbor (LKINN) location privacy protection algorithm was proposed to improve SpaceTwist.LKINN used convex hull mathematical tool to calculate the key points of K-anonymity group

and proposed an anchor selection method based on it

achieving K-anonymity security with low computational and communication costs.LKINN was based on a hybrid location privacy protection architecture

making only semi-trusted security assumptions for all members of the system

which had lax security assumptions compared to some existing research schemes.Simulation results show that LKINN can prevent semi-trusted users from stealing the location privacy of normal users and has smaller query response time and communication overhead compare to some existing schemes.

关键词

Keywords

references

万盛 , 牛犇 , 李凤华 , 等 . 位置隐私保护技术研究进展 [J ] . 通信学报 , 2016 , 37 ( 12 ): 124 - 141 .

WAN S , NIU B , LI F H , et al . Research progress on location privacy-preserving techniques [J ] . Journal on Communications , 2016 , 37 ( 12 ): 124 - 141 .

KRUMM J . Inference attacks on location tracks [C ] // 5th Springer International Conference on Pervasive Computing . 2007 : 127 - 143 .

PAULET R , KAOSAR M G , YI X , et al . Privacy-preserving and content-protecting location-based queries [J ] . IEEE Transactions on Knowledge and Data Engineering , 2014 , 26 ( 5 ): 1200 - 1210 .

GRUTESER M , GRUNWALD D . Anonymous usage of location-based services through spatial and temporal cloaking [C ] // 1st ACM International Conference on Mobile Systems,Applications,and Services (MobiSys’03) . 2003 : 31 - 42 .

CHOW C Y , MOKBEL M F , AREF W G . Casper*:query processing for location services without compromising privacy [J ] . ACM Transactions on Database Systems , 2009 , 34 ( 4 ): 1 - 48 .

CHOW C Y , MOKBEL M F , LIU X . A peer-to-peer spatial cloaking algorithm for anonymous location-based services [C ] // 14th ACM International Symposium on Advances in Geographic Information Systems (ACM-GIS’06) . 2006 : 171 - 178 .

NIU B , ZHU X Y , LI Q H , et al . A novel attack to spatial cloaking schemes in location-based services [J ] . Future Generation Computer Systems , 2015 , 49 ( 1 ): 125 - 132 .

YIU M L , JENSEN C S , MØLLER J , 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 Management of Data . 2000 : 121 - 132 .

黄毅 , 霍峥 , 孟小峰 . CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法 [J ] . 计算机学报 , 2011 , 34 ( 10 ): 1976 - 1985 .

HUANG Y , HUO Z , MENG X F . CoPrivacy:a collaborative location privacy preserving method without clocking region [J ] . Chinese Journal of Computers , 2011 , 34 ( 10 ): 1976 - 1985 .

GONG Z , SUN G , XIE X . Protecting privacy in location-based service using k-anonymity without cloaked region [C ] // Proceeding of the International Conference on Mobile Data Management (MDM’10) . 2010 : 366 - 371 .

YIU M L , JENSEN C S , MØLLER J , , et al . Design and analysis of a ranking approach to private location-based services [J ] . ACM Transactions on Database Systems , 2011 , 36 ( 2 ): 1 - 42 .

周长利 , 陈永红 , 田辉 , 等 . 保护位置隐私和查询内容隐私的路网K近邻查询方法 [J ] . 软件学报 , 2020 , 31 ( 2 ): 471 - 492 .

ZHOU C L , CHEN Y H , TIAN H , et al . Location privacy and query privacy preserving method for K-nearest neighbor query in road networks [J ] . Journal of Software , 2020 , 31 ( 2 ): 471 - 492 .

陈玉凤 , 刘学军 , 李斌 . 基于博弈论的用户相互协作的位置隐私保护方法 [J ] . 计算机科学 , 2013 , 40 ( 10 ): 92 - 97 .

CHEN Y F , LIU X J , LI B . Collaborative position privacy protection method based on game theory [J ] . Computer Science , 2013 , 40 ( 10 ): 92 - 97 .

刘振鹏 , 赵璇 , 董亚伟 , 等 . 结合锚点优选算法改进的SpaceTwist隐私保护方法 [J ] . 通信学报 , 2017 , 38 ( Z1 ): 32 - 38 .

LIU Z P , ZHAO X , DONG Y W , et al . Improved SpaceTwist privacy protection method based on anchor optimization algorithm [J ] . Journal on Communications , 2017 , 38 ( Z1 ): 32 - 38 .

周长利 , 马春光 , 杨松涛 . 基于敏感位置多样性的 LBS 位置隐私保护方法研究 [J ] . 通信学报 , 2015 , 36 ( 4 ): 129 - 140 .

ZHOU C L , MA C G , YANG S T . Research of LBS privacy preserving on Improved SpaceTwist privacy protection method based on sensitive location diversity [J ] . Journal on Communications , 2015 , 36 ( 4 ): 129 - 140 .

周宇航 , 柳毅 . 路网环境下基于双锚点的位置隐私保护方法 [J ] . 计算机应用研究 , 2022 , 37 ( 11 ): 3392 - 3395 + 3400 .

ZHOU Y H , LIU Y . Location privacy protection method based on double anchor point in road network environment [J ] . Application Research of Computers , 2022 , 37 ( 11 ): 3392 - 3395 + 3400 .

SUN R Z , XIANG G L , GAO Q W , et al . A study of location privacy protection about k-interesting points query based on double anchors [C ] // Ubiquitous Positioning,Indoor Navigation and Location-Based Services . 2018 .

LIU H Y , ZHANG S W , LI M L , et al . An effection location privacy-preseving k-anonymity scheme in location based services [C ] // IEEE International Conference on Electronic Technology,Communication and Information(ICETCI) . 2021 .

SARIEL H . On the expected complexity of random convex hulls [EB ] .

GUTTMAN A . R-trees:a dynamic index structure for spatial searching [R ] . 1984 ,14.

Views

207

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Trajectory privacy protection mechanism of obfuscating paths based on vehicles cooperation

Related Author

Ziwen ZHAO

Ayong YE

Junlin JIN

Lingyu MENG

Related Institution

No data

⁰