华东师范大学学报(自然科学版) ›› 2015, Vol. 2015 ›› Issue (5): 128-142.doi: 10.3969/j.issn.1000-5641.2015.05.011

• 隐私保护技术 • 上一篇    下一篇

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

张峰,倪巍伟   

  1. 东南大学 计算机科学与工程学院,南京211189;
    东南大学 计算机网络与信息集成教育部重点实验室,南京211189
  • 收稿日期:2015-07-09 出版日期:2015-09-25 发布日期:2015-10-08
  • 通讯作者: 倪巍伟,男,博士,教授,博士生导师,主要研究领域为复杂数据管理,数据隐私安全保护. E-mail:wni@seu.edu.cn.
  • 作者简介:张峰,男,硕士研究生,主要研究领域为数据隐私安全保护.
  • 基金资助:

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

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

ZHANG Feng,NI Wei-wei   

  • Received:2015-07-09 Online:2015-09-25 Published:2015-10-08

摘要: 空间定位与移动通信的快速发展促进了基于位置服务的普及,近邻查询作为位置服务的基本操作得到了广泛的应用.位置服务在给人们带来方便的同时也带来位置隐私保护问题,随着人们对个体隐私的日益关注,保护位置隐私近邻查询成为数据库领域研究热点之一.近年来,隐私信息检索以其能提供高强度隐私保护、无需可信第三方等优点得到了研究者的持续关注.针对已有的基于隐私信息检索的保护位置隐私近邻查询方法普遍存在预处理时间长、查询效率较低的不足,提出基于隐私信息检索的近邻查询方法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.

Key words: locationbased services, location privacy protection, private information retrieval, pseudorandom number rule