From: Thomson, Martin ^lt;*Martin.Thomson@andrew.com*>

Date: Tue Aug 24 2010 - 01:38:17 EDT

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
*