Random Sequence Coding Based Privacy Preserving Nearest Neighbor Query Method

摘要

Location based service has been widely used in people' life. It brings convenience to the people, in parallel with the risk of query user's location privacy disclosure. As a result, privacy preserving location based nearest neighbor queries witness its thriving in recent years. Private information retrieval (PIR) based solutions receives continuous attention for in privacy preserving for its merits in high level privacy protection strength and independence of the trusted third parties. However, existing PIR based methods fall short in high time consuming of encoding, querying efficiency and poor security to mode attacks. To address above issues, random sequence is introduced to encode POI data, which can resist mode attacks and reduce the time of data encoding. As a consequence, location privacy protection effectiveness is improved. Meanwhile, to accelerate query efficiency, a hash table structure is built at the server-side to store rules of POI distribution in the manner of space bitmap, which can position nearing POI quickly and reduce the I/O cost of database visiting efficiently. Theoretical analysis and experimental results demonstrates our solution's efficiency and effectiveness.