Summary contributed by Ameen Jauhar, Senior Resident Fellow at the Vidhi Centre for Legal Policy.
*Author & link to original paper at the bottom.
The authors discuss how the onslaught of location-based systems (LBS) has resulted in considerable challenges to locational privacy. Add to this the fact that most of such individual data (about locations) is stored in unknown and arguably unsecure servers, there is a need to safeguard an individual’s exact location whilst she uses a LBS. Geo-indistinguishability is the novel mechanism this paper proposes to ensure the balance where a user of a LBS discloses just enough of her approximate location to efficiently benefit from these services, while not divulging her precise location.
Existing notions of privacy
While the authors intend to provide a formal notion of privacy (i.e. geo-indistinguishability), they initiate the conversation by covering some existing ideas on privacy. These include:
- Expected distance error, which is a location-obfuscation mechanism resulting in an adversary to inaccurately determine an individual’s location. The obfuscation can occur in different ways – for instance, to throw off the tracking of an individual’s path/location, multiple paths of different users are intertwined, thus, perturbing the adversary.
- k-anonymity, which includes concealing the true identity of the user of a LBS by placing her in the midst of a set of users (k). Unlike some other notions, this focuses on protecting an individual’s identity, and consequentially, her location.
- Differential privacy, which emerges from the field of statistical databases. The notion requires the publication of aggregate data emerging from a dataset, in lieu of individual data. The difference by altering some individual data points, should be negligible and still yield the same results to a query. Given that the notion relies on aggregated information, it is inapt for situations involving a single individual.
- Location cloaking mechanism, which as the name suggests, aims at concealing the location of a user through location-ranged queries. Essentially, the objective is to cover a range of area, and conceal locations/regions within this range that the user may consider sensitive.
- Transformation based approaches make the location of a user completely invisible, rather than cloaking it. Through the use of cryptography, the data (including the query sought, as well as the location of a user), are encrypted. Using this encrypted information, the service provider can respond to a query without actually detecting the location of the user.
Geo-Indistinguishability
The probabilistic model includes multiple possible locations of a user (denoted by X). Additionally, to obfuscate the precise location, the adversary/attacker is fed variable locations (termed as reported values) to create enough disturbance to insulate the true location of the user. However, the element of probability comes into play contingent on the nature of additional (side) information that the adversary/attacker may possess, which can allow to overcome some of these disturbances, and get a relatively more accurate lock on the location of the user.
Defining geo-indistinguishability – Unlike the standard form of differential privacy which aims at completely protecting the location of a user, geo-indistinguishability is about disclosing just enough elements of such location as would allow the user to access and use the requisite LBS. Hence, while it has some commonalities with differential privacy, it uses different metrics.
Characterizations of geo-indistinguishability
The paper also elicits two key characterizations of geo-indistinguishability:
- First, it discusses the hidden functionality which allows the actual location of a user to be concealed from an attacker. Instead of disclosing the actual location, the mechanism introduces a hidden version, which can impact the conclusion(s) of the attacker in discerning the real location of a user. The extent of impact on the conclusions is affected by the distance between the actual and the hidden location. For instance, if an individual is located in Paris and using a restaurant searching app, but a hidden functionality discloses her location as London, then the attacker is likely to be completely thrown off.
- Second, the authors emphasize how geo-indistinguishability abstracts the side information. Side information essentially can be any ancillary information that may be in the possession of an attacker prior to her using a LBS. For instance, knowledge that an individual is located at an airport, yet not knowing which city’s airport. However, as the authors argue, any minimal service request will at least disclose a city, which can then be used to infer the actual location at such city’s airport. Therefore, it is necessary to abstract such side information which can be accomplished through geo-indistinguishability.
Attaining geo-indistinguishability and sample example
While concealing a singular location is one stage, it is possible for an individual to have multiple locations of interest which she may not want to divulge. For preserving the locational secrecy of these multiple points, the paper suggests two ways. First, to report on the whole set of locations by applying a common obfuscation mechanism to every single location; and second, by reporting an aggregated location, which can be the centroid of the tuple of locations that a user wants to preserve.
Given that creation of controlled noise is a prerequisite for attaining geo-indistinguishability, the authors explore different mechanisms for this with greater nuance. For this, the authors set out the mechanism for creating a continuous plane, which allows them to remap each point on such a plane to the closest point in the discrete domain, and finally, only disclose points close to the actual location of a user (area of interest).
To gauge the viability of geo-indistinguishability as a privacy guarding intervention, the authors test it on different LBS systems. These could include mildly location-sensitive and highly location-sensitive LBS applications. It is the latter where guaranteeing privacy, while delivering adequate and accurate service, is challenging. The authors also state that for a user performing multiple query request, locational privacy can be guaranteed by performing geo-indistinguishability and obtaining approximate locations to every one of the user’s locations for each query request.
The authors also contrast their method of geo-indistinguishability with other methods. For instance, they compare it to the obfuscation mechanism which also involves the creation of randomly selected location (different from the actual location of the user). However, the obfuscation method cannot abstract prior or side knowledge and is therefore, susceptible to breaches. The key difference that the authors bring forth in advocacy of geo-indistinguishability is the balance it affords in safeguarding privacy while suffering from minimal Service Quality Loss (or inaccuracies in responding to the query requests of users).
To conclude, the authors list out some possible expansions to their ongoing work on developing geo-indistinguishability.
Original paper by Miguel Andrés; Nicolás Bordenabe; Konstantinos Chatzikokolakis; and Catuscia Palamidessi: https://dl.acm.org/doi/pdf/10.1145/2508859.2516735?download=true