Measuring User Trajectory Privacy in LBSs with Adversarial Background Knowledge


Article Preview

This paper proposes a novel entropy-based metric for evaluating silent cascade which is a prevalent trajectory privacy preserving method in LBSs (location-based services). Within this measure, the trajectory privacy is quantified as the probability of the relevance between the user’s pseudonym before and after each mix-zone. After a period of time, the tracked user may take many potential trajectories from the perspective of the adversary. The user’s trajectory privacy level is calculated using information entropy. The most distinguishable aspect of the measure is to take into account the adversarial background knowledge. We develop methods to describe and quantify the adversarial background knowledge. Simulation results reflect the impact of background knowledge on the privacy level in the metric, and show that this metric is effective and valuable to measure the user’s trajectory privacy level correctly even the adversary has variable background knowledge.



Advanced Materials Research (Volumes 143-144)

Edited by:

H. Wang, B.J. Zhang, X.Z. Liu, D.Z. Luo, S.B. Zhong




C. M. Wang et al., "Measuring User Trajectory Privacy in LBSs with Adversarial Background Knowledge", Advanced Materials Research, Vols. 143-144, pp. 38-42, 2011

Online since:

October 2010




[1] Lin X, Li S P, Yang C H. Attacking algorithms against Continuous Queries in LBS and Anonymity Measurement. Journal of software, 2009, 20(4): 1058−1068.

[2] Xu T, Ying C. Location anonymity in continuous location-based services. In: Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, 2007, 1-8.


[3] Ma Z D, Frank K, Michael W. A location privacy metric for V2X communication systems. In: Proceedings of the 2009 IEEE Sarnoff Symposium, 2009, 1-6.


[4] Ma Z D, Frank K, Michael W. Measuring location privacy in V2X communication systems with accumulated information. In: Proceedings of the Sixth IEEE International Conference on Mobile Ad-hoc and Sensor Systems, 2009, 322 - 331.


[5] Edman M, Sivrikaya F, Yener B. A combinatorial approach to measuring anonymity. In: IEEE Intelligence and Security Information, 2007, 356-363.


[6] Gierlichs B, Troncoso C, Diaz C, Preneel B. Revisiting a combinatorial approach toward measuring anonymity. In: Proceedings of the 7th ACM Workshop on Privacy in the Electronic Society, 2008, 111-116.


[7] Shokri R, Freudiger J, Jadliwala M, Hubaux J P. A distortion-based metric for location privacy. In: Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society, 2009, 21-30.


[8] Huang L, Yamane L, Mastsuura K, Sezaki K. Silent Cascade: enhancing location privacy without communication QoS degradation. In: Proceedings of the Third International Conference on Security in Pervasive Computing, LNCS 3934, Springer Verlag, 2006, 165-180.


[9] Du W L, Teng Z X, Zhu Z T. Privacy-MaxEnt: Integrating background knowledge in privacy quantification. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. 2008, 459-472.