基于伪随机数加密的保护位置隐私近邻查询方法

张峰; 倪巍伟

doi:10.3969/j.issn.1000-5641.2015.05.011

基于伪随机数加密的保护位置隐私近邻查询方法

doi: 10.3969/j.issn.1000-5641.2015.05.011

张峰,
倪巍伟^,

1.
东南大学计算机科学与工程学院,南京211189;
2.
东南大学计算机网络与信息集成教育部重点实验室,南京211189

基金项目:

国家自然科学基金(61370077;61003057).

详细信息

作者简介:
张峰,男,硕士研究生,主要研究领域为数据隐私安全保护.

通讯作者:
倪巍伟,男,博士,教授,博士生导师,主要研究领域为复杂数据管理,数据隐私安全保护.

计量
- 文章访问数: 863
- HTML全文浏览量: 26
- PDF下载量: 1321
- 被引次数: 0
出版历程
- 收稿日期: 2015-07-09
- 刊出日期: 2015-09-25

Pseudorandom number encryption based location privacy preserving nearest neighbor querying

ZHANG Feng,
NI Wei-wei^,

摘要

摘要: 空间定位与移动通信的快速发展促进了基于位置服务的普及,近邻查询作为位置服务的基本操作得到了广泛的应用.位置服务在给人们带来方便的同时也带来位置隐私保护问题,随着人们对个体隐私的日益关注,保护位置隐私近邻查询成为数据库领域研究热点之一.近年来,隐私信息检索以其能提供高强度隐私保护、无需可信第三方等优点得到了研究者的持续关注.针对已有的基于隐私信息检索的保护位置隐私近邻查询方法普遍存在预处理时间长、查询效率较低的不足,提出基于隐私信息检索的近邻查询方法PRN_〖WTBX〗k〖WTBZ〗NN,通过空间加密使用户可以在本地快速查询〖WTBX〗k〖WTBZ〗近邻候选集;同时,引入伪随机数加密规则替代查询计划,抵御模式攻击的同时减少预处理时间;在数据组织方面,采用连续储存POI实体的策略避免部分块存储大量假实体的情况,实现对查询效率的提升.理论分析和实验结果验证了所提方法的有效性.
- 位置服务 /
- 位置隐私保护 /
- 隐私信息检索 /
- 伪随机数规则
Abstract: The rapid development of positioning and mobile communication promotes the popularity of locationbased services. Nearest neighbor querying witness its thriving in locationbased services. With the increasing attention people pay to individual privacy, location privacy preserving k nearest neighbor querying becomes a hot topic. In recent years, private information retrieval techniques attract increasing concerning from researchers for its merits in providing high location protection strength, as well as its independence on any trusted thirdparty. A series of methods are proposed based on PIR to surmount the problem of location privacy protection in nearest neighbors querying. Most of them suffer from heavy time cost in preprocessing as well as query process. Concerning these problems, a novel PIR based method PRN_kNN is proposed to surmount above mentioned problems.The client can pinpoint the candidate k nearest neighbor set quickly by spatial encryption. Meanwhile, a pseudorandom number encryption schema is elaborated to avoid pattern attack and reduce the workload of preprocessing.Further, continuous storage policy for POI entity is adopted to avoid storing large amounts of fake entities in some blocks, which can enhance the efficiency of preprocessing and the querying process. Theoretical and empirical analysis demonstrate the effectiveness and efficiency of our method.
- locationbased serviceslocation privacy protectionprivate information retrievalpseudorandom number rule /

HTML全文

参考文献(1)

[1]

［1］ROUSSOPOULOS N, KELLEY S, VINCENT F. Nearest neighbor queries［C］Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD’95). California, USA,1995: 7179.

［2］GRUTESER M, GRUNWAL D.Anonymous usage of location based services through spatial and temporal cloaking［C］Proceedings of the International Conference on Mobile Systems,Applications, and Services (MobiSys’03). California, USA, 2003:3142.

［3］MOKBEL M F, CHOW C Y, AREF W G. The new casper: Query processing for location services without compromising privacy［C］Proceedings of the International Conference on Very Large Data Bases (VLDB’06). Seoul, Korea, 2006: 763774.

［4］GEDIK B, LIU L. Location privacy in mobile systems: A personalized anonymization model［C］Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS’05). Ohio, USA, 2005:620629.

［5］朱怀杰, 王佳英, 王斌, 等. 障碍空间中保持位置隐私的最近邻查询方法［J］. 计算机研究与发展. 2014, 51(1): 115125.

［6］FIROOZJAEI M D, YU J, KIM H. Privacy preserving nearest neighbor search based on topologies in cellular networks［C］Proceedings of the IEEE International Conference on Advanced Information Networking and Applications Workshops. Suwon, Korea,2015: 146149.

［7］INDYK P, WOODRUFF D, Polylogarithmic private approximations and efficient matching［C］Proceedings of the Third Theory of Cryptography Conference(TCC’06), New York, USA, 2006: 245264.

［8］KHOSHGOZARAN A, SHAHABI C. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy［C］Proceedings of the International Symposium on Spatial and Temporal Databases (SSTD’07), Massachusetts, USA,2007: 239257.

［9］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］Proceedings of the IEEE International Conference on Data Engineering (ICDE’08). Cancun, Mexico, 2008: 366375.

［10］NI W W, ZHENG J W, CHONG Z H. HilAnchor:Location privacy protection in the presence of users’preferences［J］. Journal of Computer Science and Technology, 2012, 27(2): 413 427.

［11］GONG Z, SUN G, XIE X. Protecting privacy in locationbased servicesusing 〖WTBX〗k〖WTBZ〗anonymity without cloaked region［C］Proceedings of the International Conference on Mobile Data Management (MDM’10). Missouri, USA , 2010: 366371.

［12］CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private information retrieval［C］Proceedings of the Thirtysixth Annual Symposium on Foundations of Computer Science (FOCS’95).Wisconsin, USA, 1995: 4150 .

［13］KHOSHGOZARAN A, SHAHABI C, SHIRANIMEHR H. Location privacy: Moving beyond 〖WTBX〗k〖WTBZ〗anonymity, cloaking and anonymizers［J］. Knowledge and Information Systems, 2011, 26(3): 435465 .

［14］GHINITA G, KAINIS P, KHOSHGOZARAN A, et al. Private queries in location based services: Anonymizersare not necessary［C］Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD’08). British Columbia, Canada, 2008: 121132.

［15］PAPADOPOULOS S, BAKIRAS S, PAPADIAS D. Nearest neighbor search with strong location Privacy［C］Proceedings of the International Conference on Very Large Data Bases Endowment (VLDB’10). Singapore, 2010,3(1): 619629.

［16］王璐, 孟小峰. 位置大数据隐私保护研究综述［J］. 软件学报, 2014, 25(4): 693712.

［17］WILLIAMS P, SION R. Usable PIR［C］Proceedings of the Network and Distributed System Security Symposium (NDSS’08). California, USA, 2008:111.

［18］MOURATIDIS K, HADJIELEFTHERIOU M, PAPADIAS D. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring［C］Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD’05). Maryland, USA, 2005: 634645.

施引文献

资源附件(0)

访问统计