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

Pseudo-random number encryption based location privacy preserving nearest neighbor querying

空间定位与移动通信的快速发展促进了基于位置服务的普及,近邻查询作为位置服务的基本操作得到了广泛的应用.位置服务在给人们带来方便的同时也带来位置隐私保护问题,随着人们对个体隐私的日益关注,保护位置隐私近邻查询成为数据库领域研究热点之一.近年来,隐私信息检索以其能提供高强度隐私保护、无需可信第三方等优点得到了研究者的持续关注.针对已有的基于隐私信息检索的保护位置隐私近邻查询方法普遍存在预处理时间长、查询效率较低的不足,提出基于隐私信息检索的近邻查询方法 PRN_kNN,通过空间加密使用户可以在本地快速查询k近邻候选集;同时,引入伪随机数加密规则替代查询计划,抵御模式攻击的同时减少预处理时间;在数据组织方面,采用连续储存POI实体的策略避免部分块存储大量假实体的情况,实现对查询效率的提升.理论分析和实验结果验证了所提方法的有效性.

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 highlocation 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,apseudo-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.