Complete Bipartite Anonymity for Location Privacy  

作　　者：董恺 顾涛 陶先平 吕建 

机构地区：[1]State Key Laboratory for Novel Software Technology,Nanjing University [2]Institute of Computer Software,Nanjing University [3]IEEE [4]ACM [5]School of Computer Science and Information Technology,RMIT University,Melbourne,Victoria 3001,Australia [6]CCF

出　　处：《Journal of Computer Science & Technology》2014年第6期1094-1110,共17页计算机科学技术学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant Nos.61373011,91318301,and 61321491

摘　　要：Users are vulnerable to privacy risks when providing their location information to location-based services （LBS）. Existing work sacrifices the quality of LBS by degrading spatial and temporal accuracy for ensuring user privacy. In this paper, we propose a novel approach, Complete Bipartite Anonymity （CBA）, aiming to achieve both user privacy and quality of service. The theoretical basis of CBA is that： if the bipartite graph of k nearby users＇ paths can be transformed into a complete bipartite graph, then these users achieve k-anonymity since the set of ＂end points connecting to a specific start point in a graph＂ is an equivalence class. To achieve CBA, we design a Collaborative Path Confusion （CPC） protocol which enables nearby nsers to discover and authenticate each other without knowing their real identities or accurate locations, predict tile encounter location using users＇ moving pattern information, and generate fake traces obfuscating the real ones. We evaluate CBA using a real-world dataset, and compare its privacy performance with existing path confusion approach. The results show that CBA enhances location privacy by increasing the chance for a user confusing his/her path with others by 4 to 16 times in low user density areas. We also demonstrate that CBA is secure under the trace identification attack.Users are vulnerable to privacy risks when providing their location information to location-based services （LBS）. Existing work sacrifices the quality of LBS by degrading spatial and temporal accuracy for ensuring user privacy. In this paper, we propose a novel approach, Complete Bipartite Anonymity （CBA）, aiming to achieve both user privacy and quality of service. The theoretical basis of CBA is that： if the bipartite graph of k nearby users＇ paths can be transformed into a complete bipartite graph, then these users achieve k-anonymity since the set of ＂end points connecting to a specific start point in a graph＂ is an equivalence class. To achieve CBA, we design a Collaborative Path Confusion （CPC） protocol which enables nearby nsers to discover and authenticate each other without knowing their real identities or accurate locations, predict tile encounter location using users＇ moving pattern information, and generate fake traces obfuscating the real ones. We evaluate CBA using a real-world dataset, and compare its privacy performance with existing path confusion approach. The results show that CBA enhances location privacy by increasing the chance for a user confusing his/her path with others by 4 to 16 times in low user density areas. We also demonstrate that CBA is secure under the trace identification attack.

关 键 词：location privacy K-ANONYMITY path confusion query obfuscation complete bipartite anonymity 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]