A Survey on Location Privacy Preserving Techniques

作者: 卢小丹 , 张乐峰 , 熊平 :中南财经政法大学信息与安全工程学院,湖北 武汉;

关键词: 基于位置的服务位置隐私隐私保护差分隐私Location-Based Services Location Privacy Privacy Preserving Differential Privacy

摘要: 随着位置信息服务的日益普及,位置信息中包含的个人隐私信息逐渐受到了人们的广泛关注。学术界近年来对位置隐私保护问题进行了深入研究并提出了一系列实现技术。本文对位置隐私保护技术的研究进展进行综述。首先介绍基于位置的服务系统的基本框架及其面临的风险,然后将位置隐私保护技术划分为四类,包括空间模糊化、虚拟对象技术、隐私信息检索和差分隐私保护技术,详细讨论它们的基本原理及有代表性的实现方法,并在此基础上进行性能上的分析和比较。最后归纳总结位置隐私保护进一步的研究方向。

Abstract: While location-based services (LBSs) have become increasingly popular and provided enormous benefits in daily life, location privacy of individuals has been confronted with serious concerns. To address the issue, a number of location privacy preserving techniques have been proposed during the last decade. This paper surveys the state of the art of location privacy preserving techniques. Firstly, we introduce the general framework of LBS system as well as the potential threats to LBS user. Then we group the location privacy preserving techniques into four categories including space cloaking, dummy-based method, private information retrieval, and differential privacy- based method. The general principle and representative techniques of each category are discussed in detail respectively and a comparison of the techniques is presented. Finally, we summarize some new research directions and make a conclusion.

文章引用: 卢小丹 , 张乐峰 , 熊平 (2016) 位置隐私保护技术研究综述。 计算机科学与应用, 6, 354-367. doi: 10.12677/CSA.2016.66044


[1] Pan, X., Xu, J. and Meng, X. (2012) Protecting Location Privacy against Location-Dependent Attacks in Mobile Services. IEEE Transactions on Knowledge and Data Engineering, 24, 1506-1519.

[2] 陈永东. 2014盘点: 全球移动应用使用增长76% [EB/OL]. http://column.iresearch.cn/b/201501/693695.shtml, 2015-01-06.

[3] 新浪科技. Google Play开发者和应用数量首次超App Store [EB/OL]. http://tech.sina.com.cn/i/2015-01-15/doc-iawzunex8985555.shtml, 2015-01-15.

[4] 搜狐IT. 百度地图日接受请求35亿次用户量突破2亿 [EB/OL]. http://it.sohu.com/20130822/n384819513.shtml, 2013-08-22.

[5] Beresford, A.R. and Stajano, F. (2003) Location Privacy in Per-vasive Computing. IEEE Pervasive Computing, 2, 46-55.

[6] Enck, W., Gilbert, P., Han, S., Tendulkar, V., Chun, B.-G., Cox, L.P., et al. (2014) TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones. ACM Transactions on Computer Systems (TOCS), 32, 5.

[7] Mayer-Sch Nberger, V. and Cukier, K. (2013) Big Data: A Revolution That Will Transform How We Live, Work, and Think. Houghton Mifflin Harcourt, Bos-ton.

[8] Hoh, B., Gruteser, M., Xiong, H. and Alrabady, A. (2006) Enhancing Security and Privacy in Traffic-Monitoring Systems. IEEE Pervasive Computing, 5, 38-46.

[9] Matsuo, Y., Okazaki, N., Izumi, K., Nakamura, Y., Nishimura, T., Hasida, K., et al. (2007) Inferring Long-Term User Properties Based on Users’ Location History. IJCAI, 2159-2165.

[10] Wicker, S.B. (2012) The Loss of Location Privacy in the Cellular Age. Communications of the ACM, 55, 60-68.

[11] Shin, K.G., Ju, X., Chen, Z. and Hu, X. (2012) Privacy Protection for Users of Location-Based Services. IEEE Wireless Communications, 19, 30-39.

[12] Zheng, K., Shang, S., Yuan, N.J. and Yang, Y. (2013) Towards Efficient Search for Activity Trajectories. 2013 IEEE 29th International Conference on Data Engineering (ICDE), Brisbane, 8-12 April 2013, 230-241.

[13] 潘晓, 肖珍, 孟小峰. 位置隐私研究综述[J]. 计算机科学与探索, 2007(3): 268-281.

[14] 王璐, 孟小峰. 位置大数据隐私保护研究综述[J]. 软件学报, 2014(4): 693-712.

[15] Beresford, A.R., Rice, A., Skehin, N. and Sohan, R. (2011) MockDroid: Trading Privacy for Application Functionality on Smartphones. Proceedings of the 12th Workshop on Mobile Computing Systems and Applications. ACM, 49-54.

[16] Bamba, B., Liu, L., Pesti, P. and Wang, T. (2008) Supporting Anonymous Location Queries in Mobile Environments with Privacygrid. Proceedings of the 17th International Conference on World Wide Web. ACM, 237-246.

[17] Duckham, M. and Kulik, L. (2005) A Formal Model of Obfuscation and Negotiation for Location Privacy. In: Gellersen, H.-W., Want, R. and Schmidt, A., Eds., Pervasive Computing, Springer, Berlin, 152-170.

[18] Xue, M., Kalnis, P. and Pung, H.K. (2009) Location Diversity: Enhanced Privacy Protection in Location Based Services. In: Choudhury, T., Quigley, A., Strang, T. and Suginuma, K., Eds., Location and Context Awareness, Springer, Berlin, 70-87.

[19] Sweeney, L. (2002) k-Anonymity: A Model for Protecting Privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10, 557-570.

[20] Sweeney, L. (2002) Achieving k-Anonymity Privacy Protection Using Generalization and Suppression. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10, 571-588.

[21] Niu, B., Zhang, Z., Li, X. and Li, H. (2014) Privacy-Area Aware Dummy Gen-eration Algorithms for Location-Based Services. 2014 IEEE International Conference on Communications (ICC), Sydney, 10-14 June 2014, 957-962.

[22] Kido, H., Yanagisawa, Y. and Satoh, T. (2005) An Anonymous Communication Technique Using Dummies for Location-Based Services. Proceedings of the International Conference on Pervasive Services, 11-14 July 2005, 88-97.

[23] Kido, H., Yanagisawa, Y. and Satoh, T. (2005) Protection of Location Privacy Using Dummies for Location-Based Services. 21st International Conference on Data Engineering Workshops, 5-8 April 2005, 1248.

[24] Lu, H., Jensen, C.S. and Yiu, M.L. (2008) PAD: Privacy-Area Aware, Dummy-Based Location Privacy in Mobile Services. Proceedings of the 7th ACM International Workshop on Data Engineering for Wireless and Mobile Access, Vancouver, 13 June 2008, 16-23.

[25] Li, N., Li, T. and Venkatasubramanian, S. (2007) t-Closeness: Privacy beyond k-Anonymity and l-Diversity. IEEE 23rd International Conference on Data Engineering, Istanbul, 15-20 April 2007, 106-115.

[26] Ilarri, S., Mena, E. and Illarramendi, A. (2010) Location-Dependent Query Processing: Where We Are and Where We Are Heading. ACM Computing Surveys, 42, Article No. 12.

[27] Niu, B., Li, Q., Zhu, X., Cao, G. and Li, H. (2014) Achieving k-Anonymity in Privacy-Aware Location-Based Services. IEEE INFOCOM 2014-IEEE Conference on Computer Communications, Toronto, 27 April-2 May 2014, 754-762.

[28] Niu, B., Zhu, X., Lei, X., Zhang, W. and Li, H. (2013) EPS: Encounter-Based Privacy-Preserving Scheme for Location-Based Services. 2013 IEEE Global Communications Conference (GLOBECOM), Atlanta, 9-13 December 2013, 2139-2144.

[29] Zhu, X., Chi, H., Niu, B., Zhang, W., Li, Z. and Li, H. (2013) MobiCache: When k-Anonymity Meets Cache. 2013 IEEE Global Communications Conference (GLOBECOM), Atlanta, 9-13 December 2013, 820-825.

[30] Khoshgozaran, A., Shahabi, C. and Shirani-Mehr, H. (2011) Location Privacy: Going beyond K-Anonymity, Cloaking and Anonymizers. Knowledge and Information Systems, 26, 435-465.

[31] Papadopoulos, S., Bakiras, S. and Papadias, D. (2010) Nearest Neighbor Search with Strong Location Privacy. Proceedings of the VLDB Endowment, 3, 619-629.

[32] Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C. and Tan, K.-L. (2008) Private Queries in Location Based Services: Anonymizers Are Not Necessary. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, Vancouver, 9-12 June 2008, 121-132.

[33] Paulet, R., Kaosar, M.G., Yi, X. and Bertino, E. (2014) Privacy-Preserving and Content-Protecting Location Based Queries. IEEE Transactions on Knowledge and Data Engineering, 26, 1200-1210.

[34] Kushilevitz, E. and Ostrovsky, R. (1997) Replication Is Not Needed: Single Da-tabase, Computationally-Private Information Retrieval. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, 20- 22 October 1997, 364-373.

[35] Asonov, D. and Freytag, J.-C. (2003) Almost Optimal Private Information Retrieval. In: R. Dingledine and P. Syverson, Eds., Privacy Enhancing Technologies, Springer, Berlin, 209-223.

[36] Smith, S.W., Safford, D. and Ord, D.S. (2000) Practical Private Information Retrieval with Secure Coprocessors.

[37] Iliev, A. and Smith, S. (2005) More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties. Department of Computer Science, Dartmouth University, Dartmouth Computer Science Technical Report TR2005-551.

[38] Mouratidis, K. and Yiu, M.L. (2012) Shortest Path Computation with No Information Leakage. Proceedings of the VLDB Endowment, 5, 692-703.

[39] Dwork, C. (2008) Differential Privacy: A Survey of Results. In: Agrawal, M., Du, D.Z., Duan, Z.H. and Li, A.S., Eds., Theory and Applications of Models of Computation, Springer, Berlin, 1-19.

[40] 熊平, 朱天清, 王晓峰. 差分隐私保护及其应用[J]. 计算机学报, 2014, 37(1) : 101-122.

[41] Dwork, C. (2011) A Firm Foundation for Private Data Analysis. Communications of the ACM, 54, 86-95.

[42] Dwork, C., Mcsherry, F., Nissim, K. and Smith, A. (2006) Calibrating Noise to Sensitivity in Private Data Analysis. In: Halevi, S. and Rabin, T., Eds., Theory of Cryptography, Springer, Berlin, 265-284.

[43] Mcsherry, F. and Talwar, K. (2007) Mechanism Design via Differential Privacy. 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, 21-23 October 2007, 94-103.

[44] Hay, M., Rastogi, V., Miklau, G. and Suciu, D. (2010) Boosting the Accuracy of Differentially Private Histograms through Consistency. Proceedings of the VLDB Endowment, 3, 1021-1032.

[45] Gruteser, M. and Grunwald, D. (2003) Anonymous Usage of Loca-tion-Based Services through Spatial and Temporal Cloaking. Proceedings of the 1st International Conference on Mobile Systems, Applications and Services, San Francisco, 5-8 May 2003, 31-42.

[46] Chen, R., Mohammed, N., Fung, B.C., Desai, B.C. and Xiong, L. (2011) Publishing Set-Valued Data via Differential Privacy. Proceedings of the VLDB Endowment, 4, 1087-1098.

[47] Cormode, G., Pro-copiuc, C., Srivastava, D. and Tran, T.T. (2012) Differentially Private Summaries for Sparse Data. Proceedings of the 15th Interna-tional Conference on Database Theory, Berlin, 26-30 March 2012, 299-311.

[48] Li, C. and Miklau, G. (2012) An Adaptive Me-chanism for Accurate Query Answering under Differential Privacy. Proceedings of the VLDB Endowment, 5, 514-525.

[49] Li, N., Qardaji, W., Su, D. and Cao, J. (2012) PrivBasis: Frequent Itemset Mining with Differential Privacy. Proceedings of the VLDB Endowment, 5, 1340-1351.

[50] Zeng, C., Naughton, J.F. and Cai, J.-Y. (2012) On Differentially Private Frequent Itemset Mining. Proceedings of the VLDB Endowment, 6, 25-36.

[51] Friedman, A. and Schuster, A. (2010) Data Mining with Differential Privacy. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington DC, 25-28 July 2010, 493-502.

[52] Mohammed, N., Chen, R., Fung, B. and Yu, P.S. (2011) Differentially Private Data Release for Data Mining. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, 21-24 August 2011, 493-501.

[53] Smith, A. (2011) Privacy-Preserving Statistical Estimation with Optimal Convergence Rates. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, San Jose, 6-8 June 2011, 813-822.

[54] Dewri, R. (2013) Local Differential Perturbations: Location Privacy under Approximate Knowledge Attackers. IEEE Transactions on Mobile Computing, 12, 2360-2372.

[55] Andr, S.M.E., Bordenabe, N.E., Chatzikokolakis, K. and Palamidessi, C. (2013) Geo-indistinguishability: Differential Privacy for Location-Based Systems. Proceedings of the 2013 ACM SIGSAC Confe-rence on Computer & Communications Security, Berlin, 4-8 November 2013, 901-914.

[56] Chatzikokolakis, K., Palamidessi, C. and Stronati, M. (2014) A Predictive Differentially-Private Mechanism for Mobility Traces. In: De Cristofaro, E. and Murdoch, S.J., Eds., Privacy Enhancing Technologies, Springer International Publishing, 21-41.

[57] Roth, A. and Roughgarden, T. (2010) Interactive Privacy via the Median Mechanism. Proceedings of the 42nd ACM Symposium on Theory of Computing, Cambridge, 6-8 June 2010, 765-774.

[58] Xiong, P., Zhu, T., Pan, L., Niu, W. and Li, G. (2014) Privacy Preserving in Location Data Release: A Differential Privacy Approach. In: Pham, D.-N. and Park, S.-B., Eds., PRICAI 2014: Trends in Artificial Intelligence, Springer, Berlin, 183-195.

[59] Machanavajjhala, A., Kifer, D., Gehrke, J. and Venkitasubramaniam, M. (2007) l-Diversity: Privacy beyond k-Anony- mity. ACM Transactions on Knowledge Discovery from Data (TKDD), 1, Article No. 3.

[60] Xiao, X. and Tao, Y. (2007) M-Invariance: Towards Privacy Preserving Re-Publication of Dynamic Datasets. Proceedings of the 2007 ACM SIGMOD Interna-tional Conference on Management of Data, Beijing, 11-14 June 2007, 689-700.

[61] Cicek, A.E., Nergiz, M.E. and Saygin, Y. (2014) Ensuring Location Diversity in Privacy-Preserving Spatio-Temporal Data Publishing. The VLDB Journal, 23, 609-625.

[62] Page, X. and Kobsa, A. (2011) Personality-Based Privacy Management for Location-Sharing in Diverse Subpopulations. Proceedings of the 2011 iConference, Seattle, 8-11 February 2011, 736-738.

[63] Li, M., Qin, Z. and Wang, C. (2014) Sensitive Semantics-Aware Personality Cloaking on Road-Network Environment. International Journal of Security & Its Applications, 8, 133-146.

[64] Li, X.-Y. and Jung, T. (2013) Search Me If You Can: Privacy-Preserving Location Query Service. 2013 Proceedings IEEE INFOCOM, Turin, 14-19 April 2013, 2760-2768.

[65] Liang, X., Zhang, K., Shen, X. and Lin, X. (2014) Security and Privacy in Mobile Social Networks: Challenges and Solutions. IEEE Wireless Communications, 21, 33-41.

[66] Mokbel, M.F., Chow, C.-Y. and Aref, W.G. (2006) The New Casper: Query Processing for Location Services without Compromising Privacy. Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, 12-15 September 2006, 763-774.