Re: [Geopriv] location obscuring

From: Thomson, Martin ^lt;Martin.Thomson@andrew.com>
Date: Tue Aug 24 2010 - 01:38:17 EDT

Hi Jorge,

My email was a little loose in its use of language, so I can understand how you might have trouble understanding this.

More inline...

> -----Original Message-----
> From: Jorge Cuellar [mailto:jrcuellarj@googlemail.com]
> Sent: Tuesday, 24 August 2010 1:14 AM
> To: Thomson, Martin; rjsparks@nostrum.com; Hannes.Tschofenig@gmx.net;
> geopriv@ietf.org
> Subject: Re: [Geopriv] location obscuring
>
> Hi Martin, Hannes, Robert,
>
> I would like to understand you discussions on "location
> obscuring". First, let me ask you a couple of things :
>
> 1. What is your vocabulary / notation?? Assume there is no
> uncertainity, first. You have one "real location" (?) and two
> circles, a "trigger circle" and a "reported circle" (obfuscated
> circle? obfuscated location?). The centres of those two
> circles ("trigger centre / reported centre" ??) are, I guess,
> different (if not, I see some problems).

There are three locations:
        
 - the original location ("real" might be a little too strong here)
 - the reported location
 - the trigger location

The first two probably have uncertainty associated with them (imagine a circle). The trigger location doesn't have uncertainty in the same way, but can also be described with a corresponding circle enclosing it. Trigger and reported are different (though there is a slim chance that they are the same...).

> The vectors:
>
> trigger centre - real location and
> reported centre - real location
>
> let us call them "shift in reporting" / "shift for trigger" have
> lenght (or absolute value or norm) "distance to trigger centre"
> / "distance to reported centre". The direction (angle to
> some "x-axis" of those vectors are the "Direction of the shift
> in reporting" and "Direction of the shift for trigger".

That's a good description.

>
> I read the formula:
>
> Direction = 2 * pi * random
>
> as an angle (random is a random number on [0,1]). And
>
> direction * distance
>
> as a vector (in radians, of lenght distance at an angle direction).

Correct; I was using shorthand - to the detriment of clarity :(
 
> 2. Have you thought about the following problem? Suppose each day
> I commute from home to work. They are sufficiently apart so that
> the 2 "reported circles" have to be disjoint. Suppose I turn off
> my device during the trip, but torn it on as soon as I changed my
> location. All algorithms you have been discussing, as far as I
> see, provide every evening, when I come back home, a
> new "reported circle" centred around home plus a vector of fixed
> lenght with random direection. True?? Thus if anyone sees my
> provided locations all evenings he will know rather fast where
> exacly I live (by averaging the random shifts).

That's one that didn't factor into this, though perhaps it should have. Though this relies on the assumption that each night you are going to the same place, that's a pretty easy conclusion to come to.

One of the original ideas was to seed a pseudorandom number with the (real) location. A hash function would be a good substitute. This would produce the same shift vector for the same location.

The problem is that the (real) location can vary slightly, or you might move a little. If it does vary slightly, even if this is well below the obfuscation distance, then the random number is completely altered. I haven't found a good way around this particular problem. Anything you do to stabilize the direction/length of the shift vector only leads to the ability to learn what the shift vector is.
 
> 3. In the formula:
>
> Distance = sqrt(random(0, max(0, distance - existing uncertainty)))
>
> you have twice distance (one with capitals): is that intended?
> Later you use only the non-capitalized one (?)

That's a mistake, the second is the obfuscation distance, the first is the resulting shift.

> 4. I did not understand this:
> This is the same as below, except: (exept what??? and notation below?)
>
> 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);
> }

This is a replacement for the original Javascript code I used to describe the algorithm. The complete (original) is here:

  <http://www.ietf.org/mail-archive/web/geopriv/current/msg08630.html>

>
> ciao,
>
> Jorge
> ________________________________
>
> 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/
>
> > -----Original Message-----
> > From: geopriv-bounces at ietf.org [mailto:geopriv-bounces at
> ietf.org] On
> > Behalf Of Thomson, Martin
> > Sent: Tuesday, 3 August 2010 10:59 AM
> > To: geopriv at ietf.org; rjsparks at 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 at ietf.org [mailto:geopriv-bounces at
> ietf.org] On
> > > Behalf Of Thomson, Martin
> > > Sent: Saturday, 31 July 2010 2:08 AM
> > > To: geopriv at ietf.org; rjsparks at 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 at ietf.org
> > > https://www.ietf.org/mailman/listinfo/geopriv
> > _______________________________________________
> > Geopriv mailing list
> > Geopriv at ietf.org
> > https://www.ietf.org/mailman/listinfo/geopriv
_______________________________________________
Geopriv mailing list
Geopriv@ietf.org
https://www.ietf.org/mailman/listinfo/geopriv
Received on Tue, 24 Aug 2010 13:38:17 +0800

This archive was generated by hypermail 2.1.8 : Tue Aug 24 2010 - 01:36:26 EDT