research-article

Prolonging the Hide-and-Seek Game: Optimal Trajectory Privacy for Location-Based Services

Authors:

George Theodorakopoulos,

Carmela Troncoso,

Jean-Pierre Hubaux,

Jean-Yves Le BoudecAuthors Info & Claims

WPES '14: Proceedings of the 13th Workshop on Privacy in the Electronic Society

Pages 73 - 82

https://doi.org/10.1145/2665943.2665946

Published: 03 November 2014 Publication History

Abstract

Human mobility is highly predictable. Individuals tend to only visit a few locations with high frequency, and to move among them in a certain sequence reflecting their habits and daily routine. This predictability has to be taken into account in the design of location privacy preserving mechanisms (LPPMs) in order to effectively protect users when they expose their whereabouts to location-based services (LBSs) continuously. In this paper, we describe a method for creating LPPMs tailored to a user's mobility profile taking into her account privacy and quality of service requirements. By construction, our LPPMs take into account the sequential correlation across the user's exposed locations, providing the maximum possible trajectory privacy, i.e., privacy for the user's past, present location, and expected future locations. Moreover, our LPPMs are optimal against a strategic adversary, i.e., an attacker that implements the strongest inference attack knowing both the LPPM operation and the user's mobility profile.

The optimality of the LPPMs in the context of trajectory privacy is a novel contribution, and it is achieved by formulating the LPPM design problem as a Bayesian Stackelberg game between the user and the adversary. An additional benefit of our formal approach is that the design parameters of the LPPM are chosen by the optimization algorithm.

References

[1]

O. Abul, F. Bonchi, and M. Nanni. Never walk alone: Uncertainty for anonymity in moving objects databases. In 24th International Conference on Data Engineering (ICDE 2008), pages 376--385. IEEE, 2008.

Digital Library

[2]

M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. Geo-indistinguishability: Differential privacy for location-based systems. In ACM Conference on Computer and Communications Security (CCS'13), pages 901--914. ACM, 2013.

Digital Library

[3]

C. A. Ardagna, G. Livraga, and P. Samarati. Protecting privacy of user information in continuous location-based services. In 15th International Conference on Computational Science and Engineering (CSE), pages 162--169. IEEE, 2012.

Digital Library

[4]

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

Digital Library

[5]

N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. Optimal geo-indistinguishable mechanisms for location privacy. arXiv preprint arXiv:1402.5029, 2014.

[6]

K. Chatzikokolakis, C. Palamidessi, and M. Stronati. A predictive differentially-private mechanism for mobility traces. In Privacy Enhancing Technologies, pages 21--41. Springer International Publishing, 2014.

[7]

R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving user location privacy in mobile data management infrastructures. In 6th International Workshop on Privacy Enhancing Technologies (PET 2006), pages 393--412, 2006.

Digital Library

[8]

C.-Y. Chow and M. F. Mokbel. Trajectory privacy in location-based services and data publication. SIGKDD Explorations Newsletter, 13(1):19--29, June 2011.

Digital Library

[9]

M. L. Damiani, E. Bertino, and C. Silvestri. The PROBE framework for the personalized cloaking of private locations. Transactions on Data Privacy, 3(2):123--148, 2010.

Digital Library

[10]

J. Freudiger, R. Shokri, and J.-P. Hubaux. On the optimal placement of mix zones. In PETS '09: Proceedings of the 9th International Symposium on Privacy Enhancing Technologies, pages 216--234, 2009.

Digital Library

[11]

S. Gao, J. Ma, W. Shi, G. Zhan, and C. Sun. TrPF: A trajectory privacy-preserving framework for participatory sensing. IEEE Transactions on Information Forensics and Security, 8(6):874--887, June 2013.

Digital Library

[12]

G. Ghinita, M. L. Damiani, C. Silvestri, and E. Bertino. Preventing velocity-based linkage attacks in location-aware applications. In 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS 2009), pages 246--255. ACM, 2009.

Digital Library

[13]

G. Gidófalvi, X. Huang, and T. B. Pedersen. Privacy-preserving data mining on moving object trajectories. In 8th International Conference on Mobile Data Management (MDM 2007), pages 60--68. IEEE, 2007.

Digital Library

[14]

B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Achieving guaranteed anonymity in gps traces via uncertainty-aware path cloaking. IEEE Transactions in Mobile Computing, 9(8):1089--1107, 2010.

Digital Library

[15]

L. Huang, H. Yamane, K. Matsuura, and K. Sezaki. Silent cascade: Enhancing location privacy without communication QoS degradation. In Security of Pervasive Computing (SPC), pages 165--180, 2006.

Digital Library

[16]

M. E. Nergiz, M. Atzori, Y. Saygin, and B. Güç. Towards trajectory anonymization: a generalization-based approach. Transactions on Data Privacy, 2(1):47--75, 2009.

Digital Library

[17]

X. Pan, X. Meng, and J. Xu. Distortion-based anonymity for continuous queries in location-based mobile services. In 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS 2009), pages 256--265, 2009.

Digital Library

[18]

M. Piorkowski, N. Sarafijanovic-Djukic, and M. Grossglauser. CRAWDAD data set epfl/mobility (v. 2009-02-24).

[19]

L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257--286, 1989.

[20]

R. Shokri. Optimal user-centric data obfuscation. arXiv preprint arXiv:1402.3426, 2014.

[21]

R. Shokri, G. Theodorakopoulos, G. Danezis, J.-P. Hubaux, and J.-Y. Le Boudec. Quantifying location privacy: the case of sporadic location exposure. In Proceedings of the 11th international conference on Privacy enhancing technologies (PETS'11), pages 57--76, 2011.

Digital Library

[22]

R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. Le Boudec. Protecting location privacy: optimal strategy against localization attacks. In ACM Conference on Computer and Communications Security (CCS'12), pages 617--627, 2012.

Digital Library

[23]

M. Terrovitis and N. Mamoulis. Privacy preservation in the publication of trajectories. In 9th International Conference on Mobile Data Management (MDM '08), pages 65--72. IEEE, 2008.

Digital Library

[24]

G. Theodorakopoulos, R. Shokri, C. Troncoso, J.-P. Hubaux, and J.-Y. Le Boudec. Prolonging the hide-and-seek game: Optimal trajectory privacy for location-based services. arXiv preprint arXiv:1409.1716, 2014.

Digital Library

[25]

R. J. Vanderbei. Linear programming, volume 114. Springer, 2008.

[26]

T.-H. You, W.-C. Peng, and W.-C. Lee. Protecting moving trajectories with dummies. In 8th International Conference on Mobile Data Management (MDM '07), pages 278--282, May 2007.

Digital Library

Cited By

Jiang BLi MTandon R(2024)Online Context-Aware Streaming Data Release With Sequence Information PrivacyIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337800819(4390-4405)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3378008
Min MZhu HYang SXu JTong JLi SShu J(2024)Geo-Perturbation for Task Allocation in 3-D Mobile Crowdsourcing: An A3C-Based ApproachIEEE Internet of Things Journal10.1109/JIOT.2023.329578611:2(1854-1865)Online publication date: 15-Jan-2024
https://doi.org/10.1109/JIOT.2023.3295786
Kansal AMittal N(2024)Nostalgia Hub Using MERN Stack: User-Centric Design and Privacy Preservation2024 11th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions) (ICRITO)10.1109/ICRITO61523.2024.10522320(1-5)Online publication date: 14-Mar-2024
https://doi.org/10.1109/ICRITO61523.2024.10522320
Show More Cited By

Index Terms

Prolonging the Hide-and-Seek Game: Optimal Trajectory Privacy for Location-Based Services
1. Security and privacy
  1. Human and societal aspects of security and privacy
  2. Network security
2. Social and professional topics
  1. Computing / technology policy
    1. Privacy policies

Recommendations

LTPPM: a location and trajectory privacy protection mechanism in participatory sensing

The ubiquity of mobile devices has facilitated the prevalence of participatory sensing, whereby ordinary citizens use their private mobile devices to collect regional information and to share with participators. However, such applications may endanger ...
PGLP: Customizable and Rigorous Location Privacy Through Policy Graph
Computer Security – ESORICS 2020
Abstract
Location privacy has been extensively studied in the literature. However, existing location privacy models are either not rigorous or not customizable, which limits the trade-off between privacy and utility in many real-world applications. To ...
Trajectory Privacy Preserving for LBS in P2P Environment
ICBDC '18: Proceedings of the 3rd International Conference on Big Data and Computing

This paper presents a trajectory similarity measurement method based on user's local anonymous area. This method can protect the location privacy among users between each other in an anonymous group. Based on the trajectory similarity and real user's ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WPES '14: Proceedings of the 13th Workshop on Privacy in the Electronic Society

November 2014

218 pages

ISBN:9781450331487

DOI:10.1145/2665943

General Chair:
Gail-Joon Ahn
Arizona State University, USA
,
Program Chair:
Anupam Datta
Carnegie Mellon University, USA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

CCS'14

Sponsor:

SIGSAC

CCS'14: 2014 ACM SIGSAC Conference on Computer and Communications Security

November 3, 2014

Arizona, Scottsdale, USA

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
489
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jiang BLi MTandon R(2024)Online Context-Aware Streaming Data Release With Sequence Information PrivacyIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337800819(4390-4405)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3378008
Min MZhu HYang SXu JTong JLi SShu J(2024)Geo-Perturbation for Task Allocation in 3-D Mobile Crowdsourcing: An A3C-Based ApproachIEEE Internet of Things Journal10.1109/JIOT.2023.329578611:2(1854-1865)Online publication date: 15-Jan-2024
https://doi.org/10.1109/JIOT.2023.3295786
Kansal AMittal N(2024)Nostalgia Hub Using MERN Stack: User-Centric Design and Privacy Preservation2024 11th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions) (ICRITO)10.1109/ICRITO61523.2024.10522320(1-5)Online publication date: 14-Mar-2024
https://doi.org/10.1109/ICRITO61523.2024.10522320
Ma ZXu SLiu BCao J(2023)LPP2KL: Online Location Privacy Protection Against Knowing-and-Learning Attacks for LBSsIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.314207810:1(234-245)Online publication date: Feb-2023
https://doi.org/10.1109/TCSS.2022.3142078
Dong YHu YAseeri ALi DZhang R(2023)Location Inference under Temporal Correlation2023 32nd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN58024.2023.10230099(1-10)Online publication date: Jul-2023
https://doi.org/10.1109/ICCCN58024.2023.10230099
Sciancalepore SGeorge D(2022)Privacy-Preserving Trajectory Matching on Autonomous Unmanned Aerial VehiclesProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3564626(1-12)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3564626
Zheng ZLi ZJiang HZhang LTu D(2022)Semantic-Aware Privacy-Preserving Online Location Trajectory Data SharingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.318185517(2256-2271)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3181855
Zhang WJiang BLi MLin X(2022)Privacy-Preserving Aggregate Mobility Data Release: An Information-Theoretic Deep Reinforcement Learning ApproachIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.315236117(849-864)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3152361
Zhang WYin GSha YYang J(2021) Protecting the Moving User’s Locations by Combining Differential Privacy and -Anonymity under Temporal Correlations in Wireless Networks Wireless Communications and Mobile Computing10.1155/2021/66919752021(1-12)Online publication date: 2-Feb-2021
https://doi.org/10.1155/2021/6691975
Bernardini GChen HFici GLoukides GPissis S(2021)Reverse-Safe Text IndexingACM Journal of Experimental Algorithmics10.1145/346169826(1-26)Online publication date: 9-Jul-2021
https://dl.acm.org/doi/10.1145/3461698
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents