On the limitations of query obfuscation techniques for location privacy

A promising approach to location privacy is query obfuscation, which involves reporting k – 1 false locations along with the real location. In this paper, we examine the level of privacy protection provided by the current query obfuscation techniques against adversarial location service providers. As a representative and realistic implementation of query obfuscation, we focus on SybilQuery. We present two types of attacks depending upon whether or not a short-term query history is available. When history is available, using machine learning, we were able to identify 93.67% of user trips, with only 2.02% of fake trips misclassified, for the security parameter k = 5. In the absence of history, we used trip correlations to form a smaller set of trips effectively increasing the user query identification probability from 20% to about 40%. Our work demonstrates that the use of aggregate statistical information alone is not sufficient to generate simulated trips. We identify areas for improvement in the existing query obfuscation techniques.

Proceedings of the 13th International Conference on Ubiquitous Computing