Unraveling an old cloak

TLDR

Location‑based services privacy research often relies on k‑anonymity cloaking, where a query is hidden among k users to protect individual locations. This study evaluates the effectiveness of k‑anonymity cloaking against diverse adversaries and exposes inconsistencies between the cloaking mechanism and the k‑anonymity metric. The analysis shows that cloaking based on users’ locations can fail to protect privacy and may even worsen it, revealing that current k‑anonymity schemes are an inadequate, tattered cloak.

Abstract

There is a rich collection of literature that aims at protecting the privacy of users querying location-based services. One of the most popular location privacy techniques consists in cloaking users' locations such that k users appear as potential senders of a query, thus achieving k-anonymity. This paper analyzes the effectiveness of k-anonymity approaches for protecting location privacy in the presence of various types of adversaries. The unraveling of the scheme unfolds the inconsistency between its components, mainly the cloaking mechanism and the k-anonymity metric. We show that constructing cloaking regions based on the users' locations does not reliably relate to location privacy, and argue that this technique may even be detrimental to users' location privacy. The uncovered flaws imply that existing k-anonymity scheme is a tattered cloak for protecting location privacy.