计算机科学 ›› 2018, Vol. 45 ›› Issue (5): 143-146.doi: 10.11896/j.issn.1002-137X.2018.05.024

• 信息安全 • 上一篇    下一篇

基于查询概率的假位置选择算法

吴忠忠,吕鑫,李鑫   

  1. 河海大学计算机与信息学院 南京211100,河海大学计算机与信息学院 南京211100,河海大学计算机与信息学院 南京211100
  • 出版日期:2018-05-15 发布日期:2018-07-25
  • 基金资助:
    本文受国家重点研发计划(2016YFC0400910),国家重大专项(2017ZX07104-001)资助

Query Probability Based Dummy Location Selection Algorithm

WU Zhong-zhong, LV Xin and LI Xin   

  • Online:2018-05-15 Published:2018-07-25

摘要: 位置服务(Location-based Service,LBS)已经成为日常生活的重要组成部分。用户在享受位置服务带来的巨大便利的同时,也面临着巨大的隐私泄露风险。针对传统的位置隐私保护中K-匿名机制没有考虑到攻击者具有背景知识或者边信息的问题,提出了一种改进的假位置选择算法来保护位置隐私。该方法首先对样本空间进行网格划分,并基于历史查询数据计算出每个位置单元的查询概率;再结合历史查询概率为用户寻找(K-1)个假位置,使得这(K-1)个假位置的历史查询概率与用户所在位置的历史查询概率尽量相同,并且使这K个位置尽量 分散。实验结果证明了该算法在位置隐私保护方面的有效性。

关键词: 位置服务,K匿名,查询概率,假位置,边信息

Abstract: Location-based service(LBS) has become a vital part in daily life.While enjoying the convenience providedby LBS,users may have high risk of losing privacy.Traditional K-anonymity for location privacy does not consider that adversaries have some problems of background knowledge and side information.Therefore,this paper proposed an improved dummy locations selection algorithm to protect location privacy.Firstly,the space is divided into grids,and historical statistics are utilized to obtain the probability of queries of each grid of space.Then,the dummy locations are selected for users in order that the(K-1) grids has the same query probability as far as possible corresponding with the grid where the real user exists and the K locations are spread as far as possible.A series of experiments on synthetic datasets show that this algorithm is feasible and effective.

Key words: Location-based service,K-anonymity,Query probability,Dummy location,Side information

[1] KATO R,IWATA M,HARA T,et al.A dummy-based anonymization method based on user trajectory with pauses[C]∥International Conference on Advances in Geographic Information Systems.2012:249-258.
[2] CHOW C Y,MOKBEL M F,LIU X.A peer-to-peer spatial cloa-king algorithm for anonymous location-based service[C]∥Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems.ACM,2006:171-178.
[3] YIU M L,JENSEN C S,HUANG X,et al.Spacetwist:Mana-ging the trade-offs among location privacy,query performance,and query accuracy in mobile services[C]∥IEEE 24th International Conference on Data Engineering.IEEE,2008:366-375.
[4] HUA B,ZHONG C.The Privacy Preserving Technology in Data Mining[J].Microelectronics & Computer,2009,26(8):38-41.(in Chinese) 华蓓,钟诚.数据挖掘中的隐私保护技术进展分析[J].微电子学与计算机,2009,26(8):38-41.
[5] PAN X,XIAO Z,MENG X F.Survey of location privacy-preserving[J].Journal of Computer Science & Frontiers,2007,1(3):268-281.(in Chinese) 潘晓,肖珍,孟小峰.位置隐私研究综述[J].计算机科学与探索,2007,1(3):268-281.
[6] HUO Z,MENG X F.A Survey of Trajectory Privacy-preserving Techniques[J].Chinese Journal of Computers,2011,34(10):1820-1830.(in Chinese) 霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报,2011,34(10):1820-1830.
[7] BERESFORD A R,STAJANO F.Location Privacy in Pervasive Computing[J].Pervasive Computing IEEE,2003,2(1):46-55.
[8] JIANG T,WANG H J,HU Y C.Preserving location privacy in wireless lans[C]∥International Conference on Mobile Systems,Applications,and Services.2007:246-257.
[9] GRUTESER M,GRUNWALD D.Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[C]∥International Conference on Mobile Systems,Applications,and Services.DBLP,2003:31-42.
[10] KIDO H,YANAGISAWA Y,SATOH T.An anonymous communication technique using dummies for location-based services[C]∥International Conference on Pervasive Services(ICPS’05).IEEE,2005:88-97.
[11] GˇRA G,LIU L.Location Privacy in Mobile Systems:A Personalized Anonymization Model[C]∥IEEE International Conference on Distributed Computing Systems(ICDCS 2005).IEEE,2005:620-629.
[12] MA C Y,YAU D K,YIP N K,et al.Privacy vulnerability ofpublished anonymous mobility traces[C]∥ Sixteenth International Conference on Mobilie Computing and Networking.ACM, 2010:185-196.
[13] LIU X,LIU K,GUO L,et al.A game-theoretic approach forachieving k-anonymity in Location Based Services[C]∥INFOCOM,2013 Proceedings IEEE.IEEE,2013:2985-2993.
[14] LU H,JENSEN C S,MAN L Y.PAD:privacy-area aware,dummy-based location privacy in mobile services[C]∥ACM International Workshop on Data Engineering for Wireless and Mobile Access.DBLP,2008:16-23.
[15] WU Y N,ZHAO Z M,SUN C L.A anonymous Algorithm in Location Privacy Protection Based on Divide Sub Clocking Region[J].Information Security and Technology,2014,5(10):33-37.(in Chinese) 武艳娜,赵泽茂,孙传林.划分子匿名区域的 k-匿名位置隐私保护方法[J].信息安全与技术,2014,5(10):33-37.
[16] ASHOURI-TALOUKI M,BARAANI-DASTJERDI A,SELUKA A.The Cloaked-Centroid protocol:location privacy protection for a group of users of location-based services[J].Knowledge and Information Systems,2015,45(3):1-27.
[17] MOKBEL M F,CHOW C Y,AREF W G.The new Casper:query processing for location services without compromising privacy[C]∥International Conference on Very Large Data Bases.VLDB Endowment,2006:763-774.
[18] NIU B,LI Q,ZHU X,et al.Achieving k-anonymity in privacy-aware location-based services[C]∥INFOCOM,2014 Procee-dings IEEE.IEEE,2014:754-762.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!