›› 2014,Vol. 29 ›› Issue (6): 1094-1110.doi: 10.1007/s11390-014-1493-y

所属专题: Emerging Areas

• • 上一篇    下一篇

完全两分匿名实现位置隐私

Kai Dong1,2(董恺), Tao Gu3(顾涛), Senior Member, IEEE, Member, ACMXian-Ping Tao1,2(陶先平), Member, CCF, IEEE, Jian Lv1,2(吕建), Fellow, CCF, Member, ACM   

  1. 1 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210046, China;
    2 Institute of Computer Software, Nanjing University, Nanjing 210046, China;
    3 School of Computer Science and Information Technology, RMIT University, Melbourne, Victoria 3001, Australia
  • 收稿日期:2013-10-28 修回日期:2014-04-18 出版日期:2014-11-05 发布日期:2014-11-05
  • 作者简介:Kai Dong received his B.S. and M.S. degrees in computer science from Nanjing University in 2007 and 2010, respectively. He is currently a Ph.D. candidate in the Department of Computer Science at Nanjing University. His research interests include privacy preservation, mobile and pervasive computing.
  • 基金资助:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61373011, 91318301, and 61321491.

Complete Bipartite Anonymity for Location Privacy

Kai Dong1,2(董恺), Tao Gu3(顾涛), Senior Member, IEEE, Member, ACMXian-Ping Tao1,2(陶先平), Member, CCF, IEEE, Jian Lv1,2(吕建), Fellow, CCF, Member, ACM   

  1. 1 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210046, China;
    2 Institute of Computer Software, Nanjing University, Nanjing 210046, China;
    3 School of Computer Science and Information Technology, RMIT University, Melbourne, Victoria 3001, Australia
  • Received:2013-10-28 Revised:2014-04-18 Online:2014-11-05 Published:2014-11-05
  • About author:Kai Dong received his B.S. and M.S. degrees in computer science from Nanjing University in 2007 and 2010, respectively. He is currently a Ph.D. candidate in the Department of Computer Science at Nanjing University. His research interests include privacy preservation, mobile and pervasive computing.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61373011, 91318301, and 61321491.

基于位置的服务(LBS)需要用户提供位置信息,而不可信的服务提供商可能泄漏用户信息导致严重的隐私隐患.现有方法往往通过降低位置信息精度来获得隐私.本文提出了完全两分匿名(CBA)这一新方法,旨在提升隐私的同时不降低LBS的服务质量.CBA的理论基础在于:若用户路径能够组成完全两分图,那么"连接到特定起点的线段终点的集合"是一个等价类,并由此可以构造用户等价类,进而实现K匿名.我们设计了交互式路径混淆协议、用户路径预测机制和路径伪造算法来实现CBA;并使用真实数据集对CBA进行验证.实验结果表明相较于传统的路径混淆算法,CBA算法能够4到16倍的提升用户路径混淆的概率,从而极大的提升隐私.我们也证明了CBA的安全性足以应对真假路径识别攻击.

Abstract: 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 "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 users to discover and authenticate each other without knowing their real identities or accurate locations, predict the 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.

[1] Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking. In Proc. the 1st International Conference on Mobile Systems, Applications and Services (MobiSys 2003), May 2003, pp.31-42.

[2] Gedik B, Liu L. Location privacy in mobile systems: A personalized anonymization model. In Proc. the 25th International Conference on Distributed Computing Systems (ICDCS 2005), June 2005, pp.620-629.

[3] Mokbel M, Chow C, Aref W. The new Casper: Query processing for location services without compromising privacy. In Proc. the 32nd International Conference on Very Large Data Bases (VLDB 2006), Sept. 2006, pp.763-774.

[4] Kalnis P, Ghinita G, Mouratidis K, Papadias D. Preventing location-based identity inference in anonymous spatial queries. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2007, 19(12): 1719-1733.

[5] Beresford A, Stajano F. Location privacy in pervasive computing. IEEE Pervasive Computing, 2003, 2(1): 46-55.

[6] Hoh B, Gruteser M. Protecting location privacy through path confusion. In Proc. the 1st International Conference on Security and Privacy for Emerging Areas in Communications Networks (SECURECOMM 2005), September 2005, pp.194205.

[7] Hoh B, Gruteser M, Xiong H, Alrabady A. Preserving privacy in GPS traces via uncertainty-aware path cloaking. In Proc. the 14th International Conference on Computer and Communications Security (CCS 2007), October 29-November 2, 2007, pp.161-171.

[8] Palanisamy B, Liu L. MobiMix: Protecting location privacy with mix-zones over road networks. In Proc. the 27th International Conference on Data Engineering (ICDE 2011), April 2011, pp.494-505.

[9] Zheng Y, Chen Y, Xie X, Ma W. Geolife2.0: A location-based social networking service. In Proc. the 10th International Conference on Mobile Data Management: Systems, Services and Middleware (MDM 2009), May 2009, pp.357-358.

[10] Dong K, Gu T, Tao X, Lu J. Complete bipartite anonymity: Confusing anonymous mobility traces for location privacy. In Proc. the 18th International Conference on Parallel and Distributed Systems (ICPADS 2012), December 2012, pp.205212.

[11] Peddinti S, Saxena N. On the limitations of query obfuscation techniques for location privacy. In Proc. the 13th International Conference on Ubiquitous Computing (UbiComp 2011), September 2011, pp.187-196.

[12] Machanavajjhala A, Gehrke J, Götz M. Data publishing against realistic adversaries. Proc. the VLDB Endowment, 2009, 2(1): 790-801.

[13] Goldschlag D, Reed M, Syverson P. Onion routing. Communications of the ACM, 1999, 42(2): 39-41.

[14] Meyerowitz J, Choudhury R. Hiding stars with fireworks: Location privacy through camouflage. In Proc. the 15th Annual International Conference on Mobile Computing and Networking (MobiCom 2009), September 2009, pp.345-356.

[15] Sweeney L. k-anonymity: A model for protecting privacy. International Journal of Uncertainty Fuzziness and KnowledgeBased Systems, 2002, 10(5): 557-570.

[16] Sweeney L. Achieving k-anonymity privacy protection using generalization and suppression. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2002, 10(5): 571-588.

[17] Hashem T, Kulik L. "Don't trust anyone": Privacy protection for location-based services. Pervasive and Mobile Computing, 2011, 7(1): 44-59.

[18] Shokri R, Papadimitratos P, Theodorakopoulos G, Hubaux J. Collaborative location privacy. In Proc. the 8th International Conference on Mobile Adhoc and Sensor Systems (MASS 2011), Oct. 2011, pp.500-509.

[19] Christin D, Guillemet J, Reinhardt A, Hollick M, Kanhere S. Privacy-preserving collaborative path hiding for participatory sensing applications. In Proc. the 8th International Conference on Mobile Adhoc and Sensor Systems (MASS 2011), Oct. 2011, pp.341-350.

[20] Kido H, Yanagisawa Y, Satoh T. An anonymous communication technique using dummies for location-based services. In Proc. the 3rd International Conference on Pervasive Services (ICPS 2005), July 2005, pp.88-97.

[21] Krumm J. Realistic driving trips for location privacy. In Proc. the 7th International Conference on Pervasive Computing, March 2009, pp.25-41.

[22] Shankar P, Ganapathy V, Iftode L. Privately querying location-based services with SybilQuery. In Proc. the 11th International Conference on Ubiquitous Computing (UbiComp 2009), September 30-October 3, 2009, pp.31-40.

[23] Piorkowski M, Sarafijanovoc-Djukic N, Grossglauser M. A parsimonious model of mobile partitioned networks with clustering. In Proc. the 1st International Conference on Communication Systems and Networks (COMSNETS 2009), Jan. 2009, pp.1-10.

[24] Bindschaedler L, Jadliwala M, Bilogrevic I, Aad I, Ginzboorg P, Niemi V, Hubaux JP. Track me if you can: On the effectiveness of context-based identifier changes in deployed mobile networks. In Proc. the 19th Network and Distributed System Security Symposium (NDSS 2012), February 2012.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] 李明慧;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: