Subject: Re: [Geopriv] location obscuring

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 3 Aug 2010 08:58:51 +0800

I have since discovered two weaknesses in this algorithm.  The second of these I can largely attribute to Robert :)

The first is tricky.  It relies on external information.  Imagine that there is a location that is not obscured because it contains sufficient uncertainty.  If the location that triggers the creation of a new location only has very small uncertainty, the recipient can infer a great deal about the location at that instant.  

This is almost identical to the original problem.

Now, if it were not possible to learn of the uncertainty, this wouldn't be a problem.  However, there are other elements that leak information.  The location determination method does provide a fair amount of information about uncertainty.

The second is fairly simple.  The speed of the target is pretty easy to determine from this algorithm.  If it is possible to learn the obscuring distance then the speed is easy to derive from this.  (The obscuring distance is probably going to be the radius of the circle that is provided.)

I believe that these both can be addressed in the same fashion.  The point that is used for triggering is selected randomly from the uncertainty region that is provided.

This addresses the first problem by ensuring that trigger point is not related to the location provided to the recipient.

It might be sufficient to address the second problem by ensuring that a new location is not generated after a fixed movement distance.  It's possible that speed can be inferred over time, assuming that travel is linear and constant.  The larger the obfuscation distance, the harder this gets.

The following javascript implements this algorithm:

GeoShape.Fuzzer = new function(dist) {
    this.distance = dist;
    return this;
};
GeoShape.Fuzzer.prototype = {
    fuzz: function(shape) {
        var cu = shape.calculateCentroid();
        if (!cu.uncertainty) {
            cu.uncertainty = 0;
        }
        if (this.hasMoved(shape)) {
            this.reallyFuzz(cu);
        }
        return this.fuzzed;
    }, hasMoved: function(cu) {
        if (!this.triggerPoint) {
            return true;
        }
        return this.triggerPoint.distanceTo(cu.centroid) > this.distance;
    }, randomize: function(point, dist) {
        var d = Math.sqrt(Math.random()) * dist;
        var a = Math.random() * 2 * Math.PI;
        return point.centroid.movePoint(d, a);
    }, reallyFuzz: function(cu) {
        var centre = this.randomize(cu.centroid, this.distance);
        var unc = Math.max(cu.uncertainty, this.distance * 2);
        this.fuzzed = new GeoShape.Circle(centre, unc);
        this.triggerPoint = this.randomize(centre, this.distance);
    }
};

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Thomson, Martin
> Sent: Saturday, 31 July 2010 2:08 AM
> To: [email-masked]; [email-masked]; Hannes Tschofenig
> Subject: [Geopriv] location obscuring
> 
> Working on this problem throughout this week in my spare time, with the
> accordant lack of sleep that goes with an IETF meeting, I have been
> falling for a trap.  There is an underlying incorrect assumption about
> the problem that we've all fallen for.
> 
> The lie in the assumption is revealed by this statement:
> 
>  Location can change.
> 
> If that isn't enough of a clue, let me explain.
> 
> The location that we provide at any one instant might be correct for
> that instant, but we are under no obligation to ensure that the
> location is correct for the future.
> 
> Assuming as we did that location is constantly and perfectly available
> in our simulations of the obscuring algorithm, we completely fell for
> it.
> 
> Instead, here is what I propose:
> 
> For a location with centroid C[n], uncertainty U[n] and an obscuring
> distance D:
> 
>   1. We obscure location information using the simple algorithm:
> increase uncertainty to D, and move the point randomly by (D - U[x]).
> If the uncertainty is already big enough, just pass the location on.
> 
>   2. Save the original point and suppress any further reports about the
> location until the centroid moves a distance of more than D; that is,
> until | C[x+y] - C[x] | > D.
> 
>   3. Repeat ad nauseum.
> 
> You see, by suppressing location updates until the location we know
> moves more than D, then we hide location.  In between times, there is
> no promise that the location is within the uncertainty region provided,
> and nor should there be.
> 
> I think that this works.  I need some sleep and a little time with a
> piece of paper and a pen to verify this, but I think that this is the
> way forward.
> 
> --Martin
> _______________________________________________
> Geopriv mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/geopriv

---

From: "Thomson, Martin" <[email-masked]>
Date: Thu, 19 Aug 2010 09:24:28 +0800

This looks to be the right approach, with some adjustments.  Here's the algorithm I settled on:

Each time a new location is provided, that location is obscured by the chosen distance as follows:

  Direction = 2 * pi * random
  Distance = sqrt(random(0, max(0, distance - existing uncertainty)))
  Reported centre = current location centroid + direction * distance
  Reported uncertainty = max(distance, existing uncertainty)

A new location is not provided until the centroid of the current location moves a fixed distance from a trigger point.  That trigger point is chosen at the same time that the new location is selected in a similar fashion:

  Direction = 2 * pi * random
  Distance = sqrt(random(0, distance / 2))
  Trigger location = current location centroid + direction * distance

Note that the trigger is up to half the distance away - if the trigger were up to the full distance away, then a slight movement might trigger a new location.  Getting several such slight movements could result in the actual location being revealed.  This algorithm ensures that the location has to move somewhere between distance/2 and 3*distance/2 before a new location is selected.

This is the same as below, except:

    reallyFuzz: function(cu) {
        var wobble = Math.max(0, this.distance - cu.uncertainty);
        var centre = this.randomize(cu.centroid, wobble);
        var unc = Math.max(cu.uncertainty, this.distance);
        this.fuzzed = new GeoShape.Circle(centre, unc);
        this.triggerPoint = this.randomize(centre, this.distance/2);
    }

Speed is hard to predict on the micro scale, but if a straight line can be assumed (or inferred) from the data, then speed can be predicted in the aggregate.

I've used Processing [1] to produce a visualisation of this method.  It's a little big for this email, so I'll send it separately.

--Martin

[1] http://processing.org/

> Sent: Tuesday, 3 August 2010 10:59 AM
> Subject: Re: [Geopriv] location obscuring
> 
> I have since discovered two weaknesses in this algorithm.  The second
> of these I can largely attribute to Robert :)
> 
> The first is tricky.  It relies on external information.  Imagine that
> there is a location that is not obscured because it contains sufficient
> uncertainty.  If the location that triggers the creation of a new
> location only has very small uncertainty, the recipient can infer a
> great deal about the location at that instant.
> 
> Now, if it were not possible to learn of the uncertainty, this wouldn't
> be a problem.  However, there are other elements that leak information.
> The location determination method does provide a fair amount of
> information about uncertainty.
> 
> The second is fairly simple.  The speed of the target is pretty easy to
> determine from this algorithm.  If it is possible to learn the
> obscuring distance then the speed is easy to derive from this.  (The
> obscuring distance is probably going to be the radius of the circle
> that is provided.)
> 
> I believe that these both can be addressed in the same fashion.  The
> point that is used for triggering is selected randomly from the
> uncertainty region that is provided.
> 
> This addresses the first problem by ensuring that trigger point is not
> related to the location provided to the recipient.
> 
> It might be sufficient to address the second problem by ensuring that a
> new location is not generated after a fixed movement distance.  It's
> possible that speed can be inferred over time, assuming that travel is
> linear and constant.  The larger the obfuscation distance, the harder
> this gets.
> 
> 
>