Preserving query privacy with a query-based memorizing algorithm

Abstract

Query privacy is a critical concern to users of location-based services. A majority of existing query privacy protection techniques are based on the notion of k-anonymity, wherein a user's exact location is obfuscated into a spatial range containing at least k users, called the cloaking region. Thus, the user who issues the query cannot be distinguished from k-1 other users. However, when mobile users issue continuous queries using such a k-anonymity scheme, an adversary can exploit the overlapped areas of the corresponding cloaking regions to determine the query issuer with a significantly higher probability. This thesis proposes a query-based memorizing algorithm to specifically address this issue. The main idea in this thesis is to memorize the identity of the users in an anonymity set or cloaking region. When a user issues sequential location-based queries, the cloaking regions are determined such that they include a maximum number of users that have appeared in the past cloaking regions. The query-based memorizing approach is empirically evaluated by means of simulation experiments and a detailed comparative analysis with three other popular privacy protection algorithms using standard privacy metrics is performed. The results show that the proposed algorithm efficiently protects users' query privacy against the overlapped area attack, especially when users are highly mobile.