保护位置隐私和查询内容隐私的路网K近邻查询方法

位置隐私和查询内容隐私是LBS兴趣点（point of interest，简称POI）查询服务中需要保护的两个重要内容，同时，在路网连续查询过程中，位置频繁变化会给LBS服务器带来巨大的查询处理负担，如何在保护用户隐私的同时，高效地获取精确查询结果，是目前研究的难题.以私有信息检索中除用户自身外其他实体均不可信的思想为基本假设，基于Paillier密码系统的同态特性，提出了无需用户提供真实位置及查询内容的K近邻兴趣点查询方法，实现了对用户位置、查询内容隐私的保护及兴趣点的精确检索；同时，以路网顶点为生成元组织兴趣点分布信息，进一步解决了高强度密码方案在路网连续查询中因用户位置变化频繁导致的实用效率低的问题，减少了用户的查询次数，并能确保查询结果的准确性.最后从准确性、安全性及查询效率方面对本方法进行了分析，并通过仿真实验验证了理论分析结果的正确性.

Location Privacy and Query Privacy Preserving Method for K-nearest Neighbor Query in Road Networks

Location privacy and query content privacy are both critical elements in LBS querying for points of interest (POIs). For continuous queries in road networks, frequent changes of a user''s location bring huge burden of query processing to LBS server, how to release a user''s privacy information as little as possible, and obtain accurate query results efficiently are still great challenges in current researches. Taking the idea of private information retrieval (PIR), i.e. no trusted entities except the user himself, as a basic assumption, a privacy-preserving method is put forward based on homomorphic properties of Paillier cryptosystem, which the user does not need to provide his actual location or query content to LBS server in K nearest neighbor POIs query, it achieves privacy preservation in LBS and accurate retrieval of POIs. Meanwhile, takeing the vertexes in road networks as generating elements to organize the distribution information of POIs, the inefficient problem is further solved in most cryptographic query schemes, which is caused by frequent location changes in continuous query, the proposed method significantly reduces the frequency of initiating queries to LBS server without decreasing the query accuracy. Finally, the proposed method is analyzed from the aspects of accuracy, security, and efficiency, extensive experiments verify the effectiveness.