15

We are creating a website that will collect location information (points) from users. We are exploring techniques to preserve users' location privacy (e.g., often users will share their home address, which is sensitive). One option that came to mind is to obfuscate or "hash" the points before storing them in the database, eliminating the need to store these sensitive data at all.

Our basic requirements are, I believe:

  1. Given a single obfuscated point, it is not possible to derive the original point within (say) a kilometer or so, even given all the metadata associated with the point (i.e., assume the entire database is compromised).

  2. Given an arbitrarily large set of obfuscated points corresponding to the same original point, it is still not possible to derive the original point. (For example, an easy technique would be to add a random vector to the original point, but if you do this enough times, the obfuscated points will cluster around the original point.)

It would be nice if various statistical properties were preserved, though I don't know which properties are important at this stage. For example, I'd rather that obfuscated points scatter in a "natural" way rather than accumulating into a grid. However, privacy is more important than this.

Improve this question
11
  • Your requirements don't mention what sort of accuracy you wish to maintain, you only focus on the obfuscation requirement. The following algorithm trivially satisfies the requirements you listed, but is rather worthless: map each point to 0° N, 0° east. Presumably you also want to satisfy some criterion, like the obfuscated point is within x km of the actual point.
    – Llaves
    Commented Jun 20, 2012 at 4:14
  • A second question: you mention metadata and being able to reconstruct the true point if the entire database is compromised. If the metadata doesn't allow you to identify obfuscated points associated with the same "true point", then how can someone reconstruct the "true point" from repeated random samples if you can't associate them with each other? On the other hand, if the metadata does allow you to associate the points, then when you are asked to report again the location of some already obfuscated point, just return the same obfuscated value returned all the previous times.
    – Llaves
    Commented Jun 20, 2012 at 4:29
  • Do you need to be able to recreate the actual location from the hashed data, or will it just be used for confirming a person is where they say they are? If it's the latter, a one-way hash, hashing a salt + the WKT of the geometry would suffice. If it's the former, then you'll have to have some function somewhere to do the inverse transformation of your hash function - a two-way hash.
    – MerseyViking
    Commented Jun 20, 2012 at 8:56
  • Will the points be compared with other users data/other datasets as a part of the service?
    – Matthew Snape
    Commented Jun 20, 2012 at 13:34
  • @Llaves, I do actually: "within a kilometer or so". But I would hope the obfuscation level is a parameter to the algorithm. Regarding your second comment, yes, the metadata allows association of points (e.g., one user might enter the same point many times). And an algorithm that results in the same obfuscated point given the same original point is fine; but if the algorithm doesn't do that, I can't recover the original point (that's the whole reason for the question) in order to test if the same obfuscated point should be used.
    – Reid
    Commented Jun 20, 2012 at 17:24

4 Answers 4

Reset to default
7

Have a look at:

MP Armstrong, Rushton G, Zimmerman DL. Geographically masking health data to preserve confidentiality. Stat Med.1999; 18:497–525.

(citation, full text)

They discuss different 'geo-masks' for point data including displacement, rotation, random perturbation and aggregation. Although they don't discuss specific technical solutions on how to implement it, there are useful pointers to information on what you gain/loose with every approach.

For more theoretical considerations have a look at my answer to the question on similar topic.

Improve this answer
2
  • 2
    Nice reference, it is an active field so many are available. I've recommended an overview article (Mathews & Harel, 2011) in another question. I also believe the International Journal of Health Geographics has papers on it from time to time (see my citeulike library with the geomask tag). I haven't come across any tools though to do the job though, probably a useful endeavor.
    – Andy W
    Commented Jun 20, 2012 at 17:48
  • 1
    @AndyW Thanks for pointers Andy. Indeed - with the growing amount of high resolution geodata used in the public health / spatial epidemiology the problem becomes more and more relevant. I had the same feeling that practical solutions are still far behind theoretical ones - definitely a place where some nice developments can be made!
    – user173
    Commented Jun 21, 2012 at 10:38
1

You could try using Perlin noise to shift your points by a random amount, but with the advantage that points close to each other will remain close to each other, but this similarity falls off with distance. If the noise function is centred around 0, statistical analysis should still return similar data as on the source, as Perlin noise (especially the 2002 version) is a roughly Gaussian distribution.

Improve this answer
5
  • If I shift many copies of the same point, could the original point then be recovered by analyzing the shifted points?
    – Reid
    Commented Jun 20, 2012 at 20:20
  • The way I imagined it, you would use the coordinates of the point as a lookup into the noise function. So two identical points would remain coincident. You could use a third value, say the date the point was created as a lookup into a 3D Perlin noise function. Then (and I'm no statistician), it would be impractical to reconstruct the source data unless the random seed and the scale of the noise you chose was known. Even then I'm not sure it'd be practically workable.
    – MerseyViking
    Commented Jun 20, 2012 at 21:03
  • Ah, so you're making it into a hash function. It may be unsafe to assume that the random seed and scale remain secret, though; I'm assuming that the server has been entirely compromised.
    – Reid
    Commented Jun 20, 2012 at 21:05
  • Phew! OK then,I like a challenge :) Now you're really talking about physical security. You have a separate off-site machine to generate the hashes, send them over a secure connection with something like SSL. You could set up a watchdog on one or both of the servers such that if one goes down, or you press a big red button, the other automatically shuts down. If you used cloud instances, then there would be no practical way of getting anything from the other instance, short of breaking into Amazon's datacentres...
    – MerseyViking
    Commented Jun 20, 2012 at 21:15
  • As a corollary, you should only spend as much on data security as the data is worth. There are many layers you could add to your security model, but at some point you have to say enough. It'd be worth perhaps fielding this question to one of the other SE sites.
    – MerseyViking
    Commented Jun 20, 2012 at 21:20
0

This is perhaps more convoluted and involved than need be, however it may be a route to take:

Create a simple python script that takes your original input points, buffers them by a certain acceptable obfuscating distance, creates n number of random points using the buffers as a feature constraint (100, for example), and then selects one of the points using a pseudo-random number generator to use as the new obfuscated point. It would also be necessary to create a new pseudo-random number for each obfuscation.

Depending on your scenario, this could be packaged in a Toolbox and accessed as a GPService with a REST endpoint so the obfuscation occurs in memory locations and only the obfuscated point is posted to your physical database.

Improve this answer
2
  • 1
    This assumes an ArcGIS implementation, but none was mentioned in the OP. Still, an interesting solution!
    – blah238
    Commented Jun 20, 2012 at 9:32
  • 3
    This natural solution has some potential flaws upon examination: (1) several distinct points may get mapped to the same point. (2) It's easy to unmask points, as the OP shows. (3) Often points need to stand in some geographic relationship to related features: e.g., house locations ought to be near streets and not in lakes or in rail yards. Issues such as these make the problem genuinely difficult, interesting, and worthy of GIS analysis (for otherwise one could just jitter the original coordinates randomly when they are first entered into the database and be done with it).
    – whuber
    Commented Jun 20, 2012 at 14:03
0

OK, so the algorithm we are considering is as follows:

  1. Round the point to a 200-meter grid (to compensate for vagaries in geocoding).
  2. Hash the text of the point's coordinates using some cryptographic hashing algorithm (e.g., SHA2).
  3. Replace the lower-order bits of the point's coordinates (up to the desired obfuscation level of 1km) with results from the hash function.
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.