On the limitations of query obfuscation techniques for location privacy
Sai Teja Peddinti, Nitesh Saxena · 2011
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.