网络与信息安全学报 ›› 2023, Vol. 9 ›› Issue (3): 60-72.doi: 10.11959/j.issn.2096-109x.2023038

• 学术论文 • 上一篇    下一篇

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

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

  1. 中国科学技术大学网络空间安全学院，安徽 合肥 230001
  • 修回日期:2022-06-10 出版日期:2023-06-25 发布日期:2023-06-01
  • 作者简介:陈赛特（1996- ），男，浙江温州人，中国科学技术大学研究生，主要研究方向为网络安全与隐私保护
    李卫海（1975- ），男，辽宁大连人，中国科学技术大学副教授，主要研究方向包括多媒体内容安全、数据安全
    姚远志（1989- ），男，安徽望江人，博士，中国科学技术大学副研究员，主要研究方向为信息隐藏、数据安全和视频编码
    俞能海（1964- ），男，安徽无为人，中国科学技术大学教授、博士生导师，主要研究方向包括视频处理与多媒体通信、信息检索、媒体内容安全、数据安全
  • 基金资助:
    国家自然科学基金(61802357);国家重点研发计划(2018YFB0804102)

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

Saite CHEN, Weihai LI, Yuanzhi YAO, Nenghai YU   

  1. School of Cyber Science and Technology, University of Science and Technology of China, Hefei 230001, China
  • Revised:2022-06-10 Online:2023-06-25 Published:2023-06-01
  • Supported by:
    The National Natural Science Foundation of China(61802357);The National Key R＆D Program of China(2018YFB0804102)

在线阅读

18

pdf下载

90

摘要：

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

关键词: 基于位置的服务, 位置隐私保护, K匿名, 凸包, 锚点

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.

Key words: location-based service, location privacy preservation, K-anonymity, convex hull, anchor

中图分类号: 

No Suggested Reading articles found!