Subject: [Geopriv] draft-thomson-geopriv-location-obscuring

From: Cullen Jennings <[email-masked]>
Date: Sun, 7 Nov 2010 14:01:51 -0700

I don't think this work as well as you are hoping (but I was very happy happy to see this stab and and hope you continue)...

Let's take the simple case, with no updates and only a single location provided. Lets say we are working with a size value of 100m so the person is only supposed to know our location +/- 100m and the attacker knows the size is 100. [We consider cases where you don't know the size but it's really easy for the attacker to estimate so I agree with your approach that you have to assume the attacker knows the size] Now assume we know the person is constrained to a single straight road and we run the algorithm from section 3.3 and get a point. Let's just say this point happens to be 95m from the road. Now the attacker can draw a ring centered on the point with inner diameter of 95 and outer diameter of 100. The intersection of this ring and road is already only a 1/3 of uncertainty that we had hoped to provide in the case of a straight road. And this was not the attacker could guess with good chance you are in that zone - they know for a fact as long as the person is on the road you are in that zone. 

Next let consider the issues of a car traveling down a road with fairly minor variance speed (pretty much zero if you are in cruise control). In this case if the attacker just take the reported data points and feed them into a constrained Kalman filter that is constrained to stay on the road and deal with the length driven down the road as the variable, well with a shocking small number of updates you are going to have an extremely accurate position of where the car is at all points in time. 

Both of the above are sort of lame attack and just help motivate the problem. How I would go about it is first of all develop a map that for each location the map had the probability of people being there at any point in time and a base likelihood map. Just tracking things I was allowed to track would build up this map over time. I would then use particle filters - each particle would represent a current location of person you were trying to figure out the position of and the values of two random numbers used for each reporting time point. Each time a new measurement came in from, you would look at the likelihood of a given particle creating that measurement combined with likely of person being at that location given the priors from the base map. I have not done this but I suspect it would converge very fast and it would not be limited to 1-d roads or anything - it would work well in an arbitrary mesh of where people actually travel. It would run really fast even with tens of millions of particles and it's not a very high dimension space to search with this approach. If you included a binary state of if you believed the person was walking or in car for each particle it would further constrain the dynamics in a way that would help limit it even faster. 

Anyways, I  think this is one the best drafts on the Priv part of GeoPriv. Thank you - but I don't think it works quite yet or at least does not adequately describe it's limitations.

---

From: "Thomson, Martin" <[email-masked]>
Date: Mon, 8 Nov 2010 09:43:04 +0800

Hi Cullen,

The "lame" attacks that you describe are fundamental problems.

They all rely on the recipient having additional information.  And the inviolate fact is that when you provide a location, you also indirectly provide a lot of extra information.

That information is usually the data provided by a map.  That map tells the recipient where the roads are, where the population centres are, and might have all sorts of useful data.  Ultimately, there is inevitably additional information that the recipient can use to do the sorts of things you describe.

I don't think that there is a good counter for this class of problem.  Certainly not one that we can reasonably expect to build an algorithm for.  Nor do I think that this is cause to reduce the provided information further.

"Describing the limitations" is probably the only option we have.

--Martin