A hierarchical distributed trusted location service achieving location k-anonymity against the global observer

As widely known in the literature, location-based services can seriously threaten users’ privacy. Privacy-aware location-based services can be obtained by protecting the user’s identity, so that queries cannot be linked with users. A way to do this is to place a trusted third party, called Location Trusted Service, between the user and the service provider, with the role of mediating the queries coming from the users and proxying them to the provider. Before proxying the query, the Location Trusted Service builds a cloaking area that includes a sufficient number of users such that it can represent an anonymity set. This way, the identity of the user is protected against an untrusted service provider. Unfortunately, in wide-area scenarios, a centralized location-trusted service might represent a serious threat to security and privacy because the service represents a single point of failure that manages very critical and massive information. Moreover, privacy protection also against a global adversary capable to monitor the whole traffic, would result in an excessive amount of cover traffic in the network (being cover traffic necessary in this threat model). To overcome the above limitations we propose a hierarchical Location Trusted Service, whose implementation benefits from the edge–cloud paradigm. In our proposal, the territory is organized in hierarchical zones possibly managed by different autonomous organizations. Organizations that manage higher zones are involved when lower-level organizations are not able to satisfy the requests of the users. As only the lowest-level services manage exact location data, while the higher ones operate only on aggregate values, the risk associated with the single point of failure of the centralized solution is drastically reduced. Moreover, leveraging the edge–cloud implementation of the system, network traffic is better confined to the edge of the network, making the protection against the global observer feasible. A nice feature of our method is that it is parametric with respect to any existing cloaking area construction technique. However, as our method, for non-local queries, operates on aggregate data, a certain degree of approximation is introduced. To validate our proposal, we conducted an experimental campaign on a real-life map by applying our method on top of well-known cloaking area construction technique called Casper. The results turned out to be positive. For a wide range of sizes of the anonymity set, the approximation (expressed by the metric called effectiveness) is less than 10%. On the other hand, concerning the network performance, we have observed an improvement in latency and throughput ranging from 20% to 170% (depending on the size of the anonymity set). In the highest density distribution, we achieve a 66% saving in overall (non-local) traffic compared to the centralized approach.