• Skip to primary navigation
  • Skip to main content
  • LinkedIn
  • RSS
  • Twitter
Montreal AI Ethics Institute

Montreal AI Ethics Institute

Democratizing AI ethics literacy.

  • Content
    • The State of AI Ethics
    • The AI Ethics Brief
    • The Living Dictionary
    • Research Summaries
    • Columns
      • Social Context in LLM Research: the BigScience Approach
      • Recess
      • Like Talking to a Person
      • Sociology of AI Ethics
      • The New Heartbeat of Healthcare
      • Office Hours
      • Permission to Be Uncertain
      • AI Application Spotlight
      • Ethical AI Startups
    • Publications
  • Community
    • Events
    • Learning Community
    • Code of Conduct
  • Team
  • Donate
  • About
    • Our Open Access Policy
    • Our Contributions Policy
    • Press
  • Contact
  • 🇫🇷
Subscribe

Research Summary: Geo-indistinguishability: Differential privacy for location-based systems

June 28, 2020 by MAIEI

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

Category iconResearch Summaries

Want quick summaries of the latest research & reporting in AI ethics delivered to your inbox? Subscribe to the AI Ethics Brief. We write every week.
  • LinkedIn
  • RSS
  • Twitter
  • © MONTREAL AI ETHICS INSTITUTE. All rights reserved 2021.
  • This work is licensed under a Creative Commons Attribution 4.0 International License.
  • Creative Commons LicenseLearn more about our open access policy here.