轻量级K匿名增量近邻查询位置隐私保护算法

陈赛特; 李卫海; 姚远志; 俞能海

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

您当前的位置：

首页 >

文章列表页 >

轻量级K匿名增量近邻查询位置隐私保护算法

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

- 轻量级K匿名增量近邻查询位置隐私保护算法
- Location privacy protection method based on lightweight K-anonymity incremental nearest neighbor algorithm
- 网络与信息安全学报 2023年9卷第3期页码：60-72
- 作者机构：
- 作者简介：
  
  [ "陈赛特（1996- ），男，浙江温州人，中国科学技术大学研究生，主要研究方向为网络安全与隐私保护" ]
  [ "李卫海（1975- ），男，辽宁大连人，中国科学技术大学副教授，主要研究方向包括多媒体内容安全、数据安全" ]
  [ "姚远志（1989- ），男，安徽望江人，博士，中国科学技术大学副研究员，主要研究方向为信息隐藏、数据安全和视频编码" ]
  [ "俞能海（1964- ），男，安徽无为人，中国科学技术大学教授、博士生导师，主要研究方向包括视频处理与多媒体通信、信息检索、媒体内容安全、数据安全" ]
- 基金信息：
  
  国家自然科学基金;The National Natural Science Foundation of China(61802357);国家重点研发计划;The National Key R＆D Program of China(2018YFB0804102)
- DOI：10.11959/j.issn.2096-109x.2023038
  中图分类号： TP391
- 网络首发：2023-06，
  
  纸质出版：2023-06-25
- 稿件说明：
移动端阅览
陈赛特, 李卫海, 姚远志, 等. 轻量级K匿名增量近邻查询位置隐私保护算法[J]. 网络与信息安全学报, 2023,9(3):60-72.

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.
陈赛特, 李卫海, 姚远志, 等. 轻量级K匿名增量近邻查询位置隐私保护算法[J]. 网络与信息安全学报, 2023,9(3):60-72. DOI： 10.11959/j.issn.2096-109x.2023038.

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.

浏览量

207

下载量

CSCD

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

提交

工具集

关联资源

基于车辆协作的混淆路径轨迹隐私保护机制