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
> -----Original Message-----
> From: geopriv-bounces@ietf.org [mailto:geopriv-bounces@ietf.org] On
> Behalf Of Thomson, Martin
> Sent: Tuesday, 3 August 2010 10:59 AM
> To: geopriv@ietf.org; rjsparks@nostrum.com; Hannes Tschofenig
> 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.
>
> 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: geopriv-bounces@ietf.org [mailto:geopriv-bounces@ietf.org] On
> > Behalf Of Thomson, Martin
> > Sent: Saturday, 31 July 2010 2:08 AM
> > To: geopriv@ietf.org; rjsparks@nostrum.com; 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
> > Geopriv@ietf.org
> > https://www.ietf.org/mailman/listinfo/geopriv
> _______________________________________________
> Geopriv mailing list
> Geopriv@ietf.org
> https://www.ietf.org/mailman/listinfo/geopriv
_______________________________________________
Geopriv mailing list
Geopriv@ietf.org
https://www.ietf.org/mailman/listinfo/geopriv
