Towards communication-efficient private location dependent queries

Location-based services (LBS) provide useful information for users depending on their current locations. Location privacy is a major concern in LBS since the service provider may be untrustworthy or compromised. The computationally private information retrieval (CPIR)-based private LBS query scheme [5] provides strong security in location privacy, but the CPIR incurs a large amount of communication and computation cost, and large parts of the service provider's database are surrendered to the user. In this paper, we evaluate the merits of utilizing different CPIR techniques in the CPIR-based private LBS query scheme, and study the tradeoff on the computation cost, communication cost, and the extent of database disclosure by theoretical analyses and empirical experiments. The results show that by utilizing a low-expansion encryption with a two-layer version of recursive CPIR protocol, we can achieve a communication-efficient CPIR-based private LBS query scheme while keeping an acceptable computation cost, and the extent of database disclosure is also minimized.