计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 212-216.doi: 10.11896/j.issn.1002-137X.2019.08.035

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

基于GeoHash的近邻查询位置隐私保护方法

周艺华, 李广辉, 杨宇光, 侍伟敏   

  1. (北京工业大学信息学部 北京100124)
  • 收稿日期:2018-08-25 出版日期:2019-08-15 发布日期:2019-08-15
  • 通讯作者: 周艺华(1969-),男,副教授,主要研究方向为网络与信息安全,E-mail:zhouyh@bjut.edu.cn
  • 作者简介:李广辉(1992-),男,硕士生,主要研究方向为内容安全,E-mail:n3verl4nd@qq.com;杨宇光(1976-),女,教授,主要研究方向为信息安全及信息安全与其他学科的交叉学科;侍伟敏(1978-),主要研究方向为网络与信息安全、密码学以及信息安全与其他学科的交叉学科
  • 基金资助:
    北京市自然科学基金项目(4182006),国家自然科学基金项目(61572053)

Location Privacy Preserving Nearest Neighbor Querying Based on GeoHash

ZHOU Yi-hua, LI Guang-hui, YANG Yu-guang, SHI Wei-min   

  1. (Faculty of Information Technology,Beijing University of Technology,Beijing 100124,China)
  • Received:2018-08-25 Online:2019-08-15 Published:2019-08-15

摘要: 随着移动应用和定位技术的不断发展,基于位置的服务(Location-Based Services,LBS)得到了越来越广泛的应用。LBS在为人们提供便利的同时也带来了隐私泄露的风险。近年来,位置服务中的隐私保护问题得到了研究者的持续关注,特别是近邻查询中的位置隐私保护问题得到了广泛的研究。针对第三方匿名服务器缺乏可信性以及容易成为系统瓶颈的问题,提出了一种自适应位置隐私保护强度的不依赖于第三方匿名服务器的基于GeoHash的近邻查询位置隐私保护方法。该方法利用GeoHash算法对用户精确的位置坐标进行字符串编码,将二维经纬坐标转换为一维字符串;LBS服务器通过构建Trie前缀树对GeoHash编码的字符串进行匹配并将查询结果返回给用户。理论分析和实验结果表明,该算法降低了查询通讯开销,同时能够有效保护用户的位置隐私信息。

关键词: GeoHash, Trie, 基于位置的服务, 位置隐私, 字符串编码

Abstract: With the continuous development of mobile applications and location technologies,Location-Based Services has become more and more widely used.LBS brings convenience to people while also posing a risk of privacy breaches.In recent years,the issue of privacy protection in location services has received continuous attention from researchers,especially the issue of location privacy protection in neighboring queries has been extensively studied.Aiming at the lack of credibility of third-party anonymous servers and the problem of being a system bottleneck,this paper proposed a GeoHash-based neighbor query location privacy protection method that does not depend on third-party anonymous servers for adaptive location privacy protection.The method uses the GeoHash algorithm to encode the exact position coordinates of the user and convert the two-dimensional latitude and longitude coordinates into a one-dimensional string.The LBS server matches the GeoHash encoded string by constructing the Trie prefix tree and returns the query result to the user.Theoretical analysis and experimental results show that the algorithm reduces the query communication overhead and can effectively protect the user’s location privacy information

Key words: GeoHash, Location privacy, Location-Based services, String encoding, Trie

中图分类号: 

  • TP309
[1]WANG L,MENG X F.Location privacy preservation in big data era:A survey[J].Journal of Software,2014,25(4):693-712.(in Chinese) 王璐,孟小峰.位置大数据隐私保护研究综述[J].软件学报,2014,25(4):693-712.
[2]ZHANG X J,GUI X L,WU Z D.Privacy preservation for location-based services:A survey[J].Journal of Software,2015,26(9):2373-2395.(in Chinese) 张学军,桂小林,伍忠东.位置服务隐私保护研究综述[J].软件学报,2015,26(9):2373-2395.
[3]GEDIK B,LIU L.Protecting location privacy with personalized k-anonymity:Architecture and algorithms[J].IEEE Transaction on Mobile Computing,2008,7(1):1-18.
[4]GEDIK B,LIU L.A customizable k-anonymity model for protecting location privacy[C]∥Proceedings of the IEEE International conference on Distributed Computing System(ICDS’05).2005:620-629.
[5]GKOULALASDIVANIS A,KALNIS P,VERYKIOS V S.Providing K-Anonymity in location based services[M].ACM,2010.
[6]BAMBA B,LIU L,PESTI P,et al.Supporting anonymous location queries in mobile environments with privacy grid[C]∥International World Wide Web Conference WWW.2008:237-246.
[7]CHOW C Y , MOKBEL M F , LIU X . A peer-to-peer spatial cloaking algorithm for anonymous location-based service∥Acm International Symposium on Advances in Geographic Information Systems. ACM,2006.
[8]PARK G G.MobiHide:A Mobilea Peer-to-Peer System for Anonymous Location-Based Queries[M]∥Advances in Spatial and Temporal Databases.DBLP,2007.
[9]KIDO H,YANAGISAWA Y,SATOH T.An anonymous communication technique using dummies for location-based services∥ICPS’05. Proceedings. International Conference on Pervasive Services,2005.IEEE,2005.
[10]YIU M L,JENSEN C S,HUANG X,et al.SpaceTwist:Managing the Trade-Offs Among Location Privacy,Query Performance,and Query Accuracy in Mobile Services[C]∥IEEE 24th International Conference on Data Engineering,2008.ICDE 2008.IEEE,2008.
[11]MOKBEL M F,CHOW C Y,AREF W G.The New Casper:Query Processing for Location Services without Compromising Privacy[C]∥Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul,Korea,2006.
[12]KHOSHGOZARAN A,SHAHABI C,SHIRANI-MEHR H. Location privacy:going beyond K-anonymity,cloaking and anonymizers[M].Springer-Verlag New York,Inc.2011.
[13]KHOSHGOZARAN A,SHAHABI C.Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy[C]∥SSTD’07 Proceedings of the 10th international conference on Advances in spatial and temporal databases.2007:239-257.
[14]GHINITA G,KALNIS P,KHOSHGOZARAN A,et al.Private queries in location based services:Anonymizers are not necessary∥Proceedings of the ACM SIGMOD International Conference on Management of Data.Canada:ACM,2008.
[1] 王磊, 李晓宇.
基于随机洋葱路由的LBS移动隐私保护方案
LBS Mobile Privacy Protection Scheme Based on Random Onion Routing
计算机科学, 2022, 49(9): 347-354. https://doi.org/10.11896/jsjkx.210800077
[2] 张学军, 杨昊英, 李桢, 何福存, 盖继扬, 鲍俊达.
融合语义位置的差分私有位置隐私保护方法
Differentially Private Location Privacy-preserving Scheme withSemantic Location
计算机科学, 2021, 48(8): 300-308. https://doi.org/10.11896/jsjkx.200900198
[3] 王辉, 朱国宇, 申自浩, 刘琨, 刘沛骞.
基于用户偏好和位置分布的假位置生成方法
Dummy Location Generation Method Based on User Preference and Location Distribution
计算机科学, 2021, 48(7): 164-171. https://doi.org/10.11896/jsjkx.200800069
[4] 王乐业.
群智感知中的地理位置本地化差分隐私机制:现状与机遇
Geographic Local Differential Privacy in Crowdsensing:Current States and Future Opportunities
计算机科学, 2021, 48(6): 301-305. https://doi.org/10.11896/jsjkx.201200223
[5] 韩磊, 胡建鹏.
基于关键词Trie树的GCC抽象语法树消除冗余算法
Deduplication Algorithm of Abstract Syntax Tree in GCC Based on Trie Tree of Keywords
计算机科学, 2020, 47(9): 47-51. https://doi.org/10.11896/jsjkx.190600042
[6] 吴丹丹, 吕鑫.
分布式结构下基于用户协作的匿名区域构建算法
Location Anonymous Algorithm Based on User Collaboration under Distributed Structure
计算机科学, 2019, 46(4): 158-163. https://doi.org/10.11896/j.issn.1002-137X.2019.04.025
[7] 童海,白光伟,沈航.
基于双向拍卖的k-匿名激励机制
Double-auction-based Incentive Mechanism for k-anonymity
计算机科学, 2019, 46(3): 202-208. https://doi.org/10.11896/j.issn.1002-137X.2019.03.030
[8] 熊婉竹, 李晓宇.
基于匿名路由的移动位置隐私保护
Mobile Location Privacy Protection Based on Anonymous Routing
计算机科学, 2018, 45(10): 142-149. https://doi.org/10.11896/j.issn.1002-137X.2018.10.027
[9] 董玉兰,皮德常.
一种基于假数据的新型轨迹隐私保护模型
Novel Trajectory Privacy Preserving Mechanism Based on Dummies
计算机科学, 2017, 44(8): 124-128. https://doi.org/10.11896/j.issn.1002-137X.2017.08.022
[10] 陈超群,李志华.
一种面向隐私保护的密文检索算法
Privacy-preserving Oriented Ciphertext Retrieval Algorithm
计算机科学, 2016, 43(Z11): 346-351. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.080
[11] 戴佳筑,华亮.
路网环境下敏感位置匿名区域的生成方法
Method of Anonymous Area Generation for Sensitive Location Protection under Road Networks
计算机科学, 2016, 43(3): 137-144. https://doi.org/10.11896/j.issn.1002-137X.2016.03.027
[12] 马春来,单洪,马涛,顾正海.
一种基于随机森林的LBS用户社会关系判断方法
Random Forests Based Method for Inferring Social Ties of LBS Users
计算机科学, 2016, 43(12): 218-222. https://doi.org/10.11896/j.issn.1002-137X.2016.12.040
[13] 陈业纲,徐则同.
基于聚类、空间分集和轨迹连续的实时定位算法
Real-time Positioning Algorithm Based on Clustering,Spatial Diversity and Continuous Trajectory
计算机科学, 2015, 42(8): 283-287.
[14] 易显天,徐 展,张 可,郭承军.
一种基于受限网络的移动对象索引结构
Index Structure for Moving Objects Based on Restricted Network
计算机科学, 2015, 42(5): 211-214. https://doi.org/10.11896/j.issn.1002-137X.2015.05.042
[15] 王鹏飞,李千目,朱保平.
基于增量近邻查询的位置隐私保护方法
Location Privacy Protection Method Based on Incremental Nearest Neighbor Query
计算机科学, 2015, 42(3): 158-161. https://doi.org/10.11896/j.issn.1002-137X.2015.03.033
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!