National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
Yuling Chen
Guizhou Provincial Key Laboratory of Public Big Data, Guizhou University, Guiyang, China
Guangcan Yang
National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
Yixian Yang
National Engineering Laboratory for Disaster Backup and Recovery, Information Security Center, School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing, China
Trajectory k-anonymity is a prevalent technique for protecting trajectory privacy. However, the existing techniques for generating fake trajectories can be easily broken by an adversary because of the failure to capture the probabilistic features and geographic features of the trajectories. They also reduce data availability. Thus, this paper proposes a location recombination mechanism (LRM) for achieving trajectory k-anonymity privacy protection. First, we propose a metric that measures the location pair similarity between location pairs. Based on this metric, we select sampling locations and divide locations into different equivalent probability classes. Locations in one equivalent probability class have the same probability as one corresponding base location. Then, we also introduce two metrics that measure the probabilistic similarity and geographic similarity between locations. Based on these metrics, we design algorithms to generate fake trajectories. These algorithms can recombine locations sampled from each equivalent probability class into trajectories. All of these trajectories meet the privacy protection requirements for both base trajectories and sampling trajectories. Finally, we evaluate our scheme thoroughly with real-world data. The results show that our method can protect the privacy of base trajectories and sampling trajectories and achieve a better performance of service provider utility and data availability than other schemes.
