Maede ASHOURI-TALOUKI, Ahmad BARAANI-DASTJERDI, Ali Aydın SELÇUK

Preserving location privacy for a group of users

Location privacy is an interesting problem that has been receiving considerable attention. This problem has been widely discussed from the individual point of view; however, there exist only a few works that support location privacy for a group of users. In this paper we consider the problem of supporting location privacy for a group of users during the use of location-based services (LBSs). We assume a group of users who want to benefit from a LBS and find the nearest meeting place that minimizes their aggregate distance. Each user in this scenario wants to protect his or her location from the LBS, outside attackers, and other group members. We show that individual solutions for location privacy cannot be directly applied to the group location privacy problem and a special solution must be developed. We identify the privacy issues for this group scenario and propose a resource-aware solution in order to satisfy these group privacy issues. Our solution is based on secure multiparty computation and the anonymous veto network protocol. The proposed protocol decreases the number of group queries to a large extent, as it only sends a single query to the LBS. Consequently, the LBS overhead to evaluate the query and the size of the LBS result are significantly decreased. The proposed protocol also protects the LBS from the excessive disclosure of points of interest and the LBS provider only needs to apply an existing private nearest neighbor (NN) query algorithm instead of an aggregate NN query algorithm. The performance and security analysis show that the protocol is secure against a partial collusion attack and a denial-of-service attack in a malicious model.

Anahtar Kelimeler:

Location privacy, secure multiparty computation, location-based service, AV-net

Preserving location privacy for a group of users

Keywords:

Location privacy, secure multiparty computation, location-based service, AV-net,

PDF

___

G. Zhong, U. Hengartner, “A distributed k-anonymity protocol for location privacy”, IEEE International Conference on Pervasive Computing and Communications, pp. 253–262, 2009.
P. Bhaskar, S.I. Ahamed, “Privacy in pervasive computing and open issues”, 2nd International Conference on Availability, Reliability and Security, pp. 147–154, 2007.
M. Langheinrich, “A privacy awareness system for ubiquitous computing environments”, Proceedings of the 4th International Conference on Ubiquitous Computing, pp. 237–245, 2002.
A. Solanas, J. Domingo-Ferrer, A. Mart´ınez-Ballest´ e, “Location privacy in location-based services: beyond TTPbased schemes”, Proceedings of the 1st International Workshop on Privacy in Location-Based Applications, pp. 12–23, 2008.
D. Papadias, Y. Tao, K. Mouratidis, C.K. Hui, “Aggregate nearest neighbor queries in spatial databases”, ACM Transactions on Database Systems, Vol. 30, pp. 529–576, 2005.
T. Hashem, L. Kulik, R. Zhang, “Privacy preserving group nearest neighbor queries”, Proceedings of the 13th International Conference on Extending Database Technology, pp. 489–500, 2010.
W. Diffie, M.E. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, Vol. 22, pp. 644–654, 1976.
M.F. Mokbel, C.Y. Chow, W.G. Aref, “The new Casper: query processing for location services without compromising privacy”, Proceedings of the 32nd International Conference on Very Large Data Cases, pp. 763–774, 2006. P. Kalnis, G. Ghinita, K. Mouratidis, D. Papadias, “Preserving location-based identity inference in anonymous spatial queries”, IEEE Transactions on Knowledge and Data Engineering, Vol. 19, pp. 1719–1733, 2007.
B. Bamba, L. Liu, P. Pesti, T. Wang, “Supporting anonymous location queries in mobile environments with privacygrid”, Proceedings of the 17th International Conference on World Wide Web, pp. 237–246, 2008.
M. Gruteser, D. Grunwald, “Anonymous usage of location-based services through spatial and temporal cloaking”, Proceedings of the 1st International Conference on Mobile Systems, Applications and Services, pp. 31–42, 2003.
U. Hengartner, P. Steenkiste, “Protecting access to people location information”, Proceedings of the 1st International Conference on Security in Pervasive Computing, pp. 25–38, 2003.
L. Sweeney, “k-Anonymity: a model for protecting privacy”, International Journal of Uncertainty, Fuzziness and Knowledge Based Systems, Vol. 10, pp. 557–570, 2002.
R. Srikanth, L.K. Awasthi, “Privacy for mobile users in location-based services”, MES Journal of Technology and Management, Vol. 2, pp. 93–98, 2011.
A. Solanas, A. Mart´ınez-Ballest´ e, “Privacy protection in location-based services through a public-key privacy homomorphism”, Proceedings of the 4th European Conference on Public Key Infrastructure: Theory and Practice, pp. 362–368, 2007.
C. Chow, M.F. Mokbel, X. Liu, “A peer-to-peer spatial cloaking algorithm for anonymous location-based services”, Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, pp. 171–178, 2006.
A. Solanas, A. Mart´ınez-Ballest´ e, “A TTP-free protocol for location privacy in location-based services”, Computer Communications Journal, Vol. 31, pp. 1181–1191, 2008.
T. Hashem, L. Kulik, “Don’t trust anyone: privacy protection for location-based services”, Journal of Pervasive Mobile Computing, Vol. 7, pp. 44–59, 2011.
C.A. Ardagna, M. Cremonini, E. Damiani, S. De Capitani di Vimercati, P. Samarati, “An obfuscation-based approach for protecting location privacy”, IEEE Transactions on Dependable and Secure Computing, Vol. 8, pp. 13–27, 2011.
M.L. Yiu, C.S. Jensen, X. Huang, H. Lu, “Spacetwist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile services”, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, pp. 366–375, 2008.
R. Dewri, “Location privacy and attacker knowledge: who are we fighting against?”, 7th International ICST Conference on Security and Privacy in Communication Networks, pp. 1–20, 2011.
G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, K.L. Tan, “Private queries in location based services: anonymizers are not necessary”, Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp.121–132, 2008.
F. Olumofin, P.K. Tysowski, I. Goldberg, U. Hengartner, “Achieving efficient query privacy for location based services”, Proceedings of the 10th International Conference on Privacy Enhancing Technologies, pp. 93–110, 2010. G. Ghinita, P. Kalnis, S. Skiadopoulos, “PRIV ´ E: Anonymous location-based queries in distributed mobile systems”, Proceedings of the 16th International Conference on World Wide Web, pp. 371–389, 2007.
G. Ghinita, P. Kalnis, S. Skiadopoulos, “MobiHide: a mobile peer-to-peer system for anonymous location-based queries”, Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases, pp. 221–238, 2007.
T. Okamoto, S. Uchiyama, “A new public-key cryptosystem as secure as factoring”, International Conference on the Theory and Application of Cryptographic Techniques, pp. 308–318, 1998.
H. Hu, J. Xu, “Non-exposure location anonymity”, Proceedings of the 2009 IEEE International Conference on Data Engineering, pp. 1120–1131, 2009.
K. Deng, S. Sadiq, X. Zhou, H. Xu, G.P.C. Fung, Y. Lu, “On group nearest group query processing”, IEEE Transactions on Knowledge and Data Engineering, Vol. 24, pp. 295–308, 2012.
Y. Huang, R. Vishwanathan, “Privacy preserving group nearest neighbour queries in location-based services using cryptographic techniques”, Proceedings of the IEEE Global Communications Conference, pp. 1–5, 2010.
T. Hashem, L. Kulik, “Safeguarding location privacy in wireless ad-hoc networks”, Proceedings of the 9th International Conference on Ubiquitous Computing, pp. 372–390, 2007.
A.C. Yao. “How to generate and exchange secrets”, 27th IEEE Symposium on Foundations of Computer Science, pp. 162–167, 1986.
O. Goldreich, S. Micali, A. Wigderson, “How to play any mental game or a completeness theorem for protocols with honest majority”, 9th ACM Conference on Theory of Computing, pp. 218–229, 1987.
F. Hao, P. Ryan, P. Zielinski, “Anonymous voting by 2-round public discussion”, IET Information Security, Vol. 4, pp. 62–67, 2010.
F. Hao, P. Zielinski, “A 2-round anonymous veto protocol”, 14th International Workshop on Security Protocols, pp. 202–211, 2006.
F. Hao, P. Zielinski, “The power of anonymous veto in public discussion”, Springer Transactions on Computational Sciences Journal, Vol. 5430, pp. 41–52, 2009.
G. Zhong, I. Goldberg, U. Hengartner. “Louis, Lester and Pierre: three protocols for location privacy”, Proceedings of the 7th International Conference on Privacy Enhancing Technologies, pp. 62–76, 2007.
C.P. Schnorr, “Efficient signature generation by smart cards”, Journal of Cryptology, Vol. 4, pp. 161–174, 1991.
B. Yang, H. Nakagawa, I. Sato, J. Sakuma, “Collusion-resistant privacy-preserving data mining”, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 483–492, 2010.