Enhanced Privacy Preserving Group Nearest Neighbor Search

Abstract

Group k-nearest neighbor (kGNN) search allows a group of n mobile users to jointly retrieve k points from a location-based service provider (LSP) that minimizes the aggregate distance to them. We identify four protection objectives in the privacy preserving kGNN search: (i) every user's location should be protected from LSP; (ii) the group's query and the query answer should be protected from LSP; (iii) LSP's private database information should be protected from users; (iv) every user's location should be protected from other users in the group. We design two privacy preserving solutions under two types of threat model to the privacy preserving kGNN search in the full user collusion environment, where any n - 1 users in the group may collude to infer the location of the remaining user. Our solutions do not rely on heavy pre-computation on LSP like previous works. Though we consider kGNN, the proposed privacy preserving solutions can be easily adopted to any group query as it treats the query answering (i.e., kGNN) as a black box. Theoretical and experimental analysis suggest that our solutions are highly efficient in both communication cost and user computational cost while incurring some reasonable overhead on LSP.