A Location Privacy-Preserving Protocol Based on Homomorphic Encryption and Key Agreement

Location-based services (LBS) bring so much convenience to our daily life. However they have incurred serious location privacy problems. K-anonymity is the one of most popular privacy-preserving methods. The method relying on a trusted third party (TTP) might cause the TTP to become a performance bottleneck. So TTP-free protocols are proposed. But existing TTP-free protocols cannot resist attacks from multiple users colluding with a LBS provider. To solve the problems, this paper proposes a novel location privacy-preserving protocol. The protocol uses key agreement to construct the perturbations which can be removed on the whole. The perturbations are used to disguise real locations, meanwhile, they do not affect LBS service quality. With the help of homomorphic encryption, the LBS provider can compute the centroid of a companion set while it does not know the locations of the members in the set. The analysis shows that the protocol can resist location privacy attacks from insiders and outsiders, especially from multiple users colluding with the LBS provider. The protocol achieves high service quality while providing strong location privacy protection for LBS.