Securing GPS data using Geo-indistinguishability

Imagine yourself walking on the busy streets of Rome, trying to decide which monument to visit next. Not so long ago, we would nicely ask the locals for their recommendations and would spend quite an amount of time trying to locate them. Nowadays, we can simply grab our smartphone and look not only for monuments but also for restaurants, stores… We can find thousands of apps that provide such services by using users’ geographical information. These services are also known as Location-based systems (LBS).

Even though these kinds of systems have many benefits for the users, some privacy concerns might arise, as we exposed in Location data: can they be really anonymous?. The LBS provider can link the users with their visited locations and, therefore, it is possible to infer sensitive information. For this reason, it is important to develop mechanisms that protect the privacy of the user, while preserving the usefulness of the provided service.

Geo-indistinguishability

There are many different techniques to provide location privacy and each of them is adequate depending on the circumstances. In this post, we will cover Geo-indistinguishability^[1], which is one of the techniques that aims to solve the privacy issues mentioned above.

To illustrate the concept of Geo-indistinguishability, let us go back to our previous example, where we tried to find monuments close to us in Rome. If we are at the Basilica of Santa Maria Maggiore, instead of sending that exact position to the LBS, we could send any other position within a certain radius. For example, we could say we are at the Pantheon.

That is, instead of disclosing our exact position x to the LBS, it could be possible to add certain noise to the location, obtaining a new approximate location z within a radius r from x. Any other user located at any other position x’ would have the same probability of sending the same approximate location z within the same radius r. That makes x and x’ statistically indistinguishable and thus, the privacy of the users is preserved.

Mathematically, given two real locations x and x’, and a obfuscated location z, geo- indistinguishability implies:

Where ϵ is the privacy parameter. The bigger it is, the less privacy will be achieved.

Where is the trade-off between privacy and utility?

The first question that comes to mind with geo-indistinguishability and GPS anonymization techniques in general is how much utility am I trading for privacy? Going back to our previous example again, it is obvious that if we are at position x (the Basilica of Santa Maria Maggiore) and we send the LBS an anonymized location z (the Pantheon), we will be missing some points of interest near us. Moreover, the new location z could not make sense at all (eg. in the sea, on top of a mountain, etc). Some solutions have been proposed to address this issue, such as opting for a remapping mechanism^[2].

Representation of the trade-off between privacy and utility. Sending our new fake location z implies that we will lose some points of interest near us (crossed in blue)

Although simple and easy to implement, it has been proved that Geo-indistinguishability might always not be suitable for all situations, since it can imply an important loss of utility in certain scenarios. For example, if we wished to achieve GeoInd with ϵ∗ = 0.01 between locations in an area of 100m, we would have an average loss of 20 kilometers[3]. For this reason, it is important to analyze the problem and choose the correct anonymization technique.

Gradiant is currently taking part in the H2020 project INFINITECH (Grant Agreement 856632), researching and developing different anonymization algorithms as a part of an anonymization tool which will cover location privacy.

References

^[1] Andrés, E. Miguel  et al. Geo-Indistinguishability: Differential Privacy for Location-Based Systems.

^[2] Chatzikokolakis, K. et al. Efficient Utility Improvement for Location Privacy

^[3] Oya, S. et al. Is Geo-Indistinguishability What You Are Looking for?

“This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 856632”.

Author: Sara El Kortbi Martínez, researcher-engineer at Gradiant