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