Subject: Re: [Geopriv] location obscuring

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 24 Aug 2010 13:38:17 +0800

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:[email-masked]]
> Sent: Tuesday, 24 August 2010 1:14 AM
> To: Thomson, Martin; [email-masked]; [email-masked];
> [email-masked]
> 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

---

From: Jorge Cuellar <[email-masked]>
Date: Thu, 26 Aug 2010 13:49:10 +0200

Fine! I still have two questions:

1. Is it safe to assume that the algorithm that generates
the reported locations has a memory? It seems that the
algorithm checks somehow, (it doesn't matter how) if we are
still fine with the last reported location we still report
it, and if not, we report a new location. It would be good
if we could rely on this: you will be giving much more
information away if you did not remember what your last
reported location was.

2. Good random number generation is not easy. Shall we say
something about it? (Most hashes are fine: but hashes of
what?)

-----------------------------------------------------------
I would prefer an algorithm that tells that I am in Berlin
(say a circle with center in the center of Berlin) than one
that gives each time a different circle with a center
randomly distributed around my real location. The averages
(plus some clustering algorithms) of those values would
provide a high precision on the places I visit in Berlin.

> 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.

Thus I need one algorithm that chooses out of my location a
"landmark" that is a good approximation of my location (and
of all locations in a neighborhood).

The idea is: if I am "clearly closer" to a landmark: choose it.
If not, choose the two closest landmarks. Then I am "clearly
between those two landmarks".  I will choose anyone
either memoryless with prob 1/2 or with a bias toward my
previously reported location.

Consider the following algorithm sketch:

Divide the problem in two steps:

1. What are the locations I will be willing to have a
possible reported locations?  The centers of those possible
reported locations are called "landmarks".

2. Given a real measurement, how to choose a landmark and
therefore a reported location?

1st step:

Given (input) a reported uncertainty that one wants to
meet, first associate to them a grid G which is a set of
points ("landmarks" or "possible reported centers") and a
set A (atlas) of regions (say, circles, the "possible
reported locations"). Notice that the associations:

  uncertainty --> G = grid = Set of "landmarks" or
                            "possible reported locations"

  uncertainty --> A = atlas = Set of "possible reported
                             locations"

are independent of any measured location. It is possible to
publish, for given value ranges of uncertainty, the list G
of landmarks (or, even better, the list of "blocks", see
below).

An atlas is a set of regions that cover all possible places
(locations with uncertainty 0). I would restrict the
possible set of atlases by saying that the have to have a
certain degree of coverage (or degree of overlap). Although
not necessarily every point has to be in several regions of
the atlas, the overlaps between neighboring regions has to
be relatively large. This will be discussed later in more
detail.

This can be done in many ways. For instance:

a. the "possible reported centers" could be just the points
in a grid in some geographic coordinate system (say,
latitude and longitude) with a given degree of precision
(significant digits). For instance: represent the latitude
and longitude of a point as a number between 0 and 1 in
base two (more convenient than base 10). Consider first all
points with 1 decimal, than all with two decimal places,
than all with three, etc. For each point considered (this
is one "possible reported center") create the corresponding
"possible reported locations" (which can be, say, a
circle). You continue adding points until you get the degree
of coverage wanted.

b. You can choose the grid points to be the centers of
"large" cities, towns, or other important landmarks in
maps. Again, we call those points in the maps "landmarks".
Assume you have an ordering of landmarks by importance
(say: size of the city in habitants). Given a certain
targeted uncertainty, create G and A as follows: add a
landmark as a "possible reported center" and the
corresponding "possible reported locations" as long as you
need it to cover the area in question with the expected
degree of coverage.

For many applications I myself would choose in Germany the
reported uncertainty to be, say, 100 or 300 km and the
"possible reported centers" to be the center of some "large
cities".

2nd step:

Now: given a measured location, a grid G and an atlas A,
the question is how to choose the region R in the atlas
that will be used as reported location.

You can do it like this:
if the measured location is in only one region R, report
this as the location.

Else, determine c1 and c2 the two closest landmarks, i.e,
"possible reported centers": at measured distances d1 and
d2. If d1 is "clearly smaller" than d2, choose c1, and
report the region centered at c1. "Clearly smaller" means
that the quotient d1/d2 is less than 0.8 (or other some
positive number, smaller than 1, to be chosen carefully a
priori). Similarly for d2/d1<1.3. If d1 and d2 are "about
the same", choose c1 with probability 1/2, c2 with
probability 1/2. In this case we say that the point is
"clearly between the two landmarks c1 and c2.

The idea is that each point is either "close to one
landmark" or "between two landmarks". This partitions the
whole space into connected (even: convex) "blocks" (let us
call them so). Thus all points in one block are all clearly
closer to the same landmark or clearly between two given
landmarks.

What do you think?
-- Jorge

---

From: Jorge Cuellar <[email-masked]>
Date: Fri, 27 Aug 2010 18:08:33 +0200

There is a simpler version of (a slight modification) of
the algorithm I proposed with the grid.

The idea again is to have a set of "landmarks" that are the
"centers" of regions used as "possible reported locations".

Consider the area you want to tile to be a flat surface. (A
tessellation or tiling of a surface is a collection of
figures that fills the original one with no overlaps or
gaps). We are interested on tiling with approximately
regular triangles of approximately the same size. The flat
case this is easy: tile the plane in the standard way with
regular (equilateral) triangles of the same size. In this way
you get, with a suitable choice of coordinates, the grid
points:

 (e x n, d x m) (n, and m range over the integers,
                 with n+m = even
                 e and d are numbers with
                    d/e =((square root of three) /2),
                 where "x" represents multiplication and
                  "/" division).

An example is given in the figure below, where the grid
points are shown as asterisks "*". Thus, the points have
coordinates (starting, say, at the bottom left with (0,0):

  (0,0),  (0,2d),  (0,4d),  ...
  (e,d),  (e,3d),  (e,5d),  ...
  (2e,0), (2e,2d), (2e,4d), ...
  (3e,d), (3e,3d), (3e,5d), ...

Those points G ("*") are the "landmarks".

          *                   *                   *

*                   *                   *                   *

          *                   *                   *

*                   *                   *                   *

Insert now the midpoints of the sides of the triangle. They
are(shown in the figure below as dots, ".".  Each of those
points is equidistant to exactly two landmarks.

.         *         .         *         .         *         .

     .         .         .         .         .         .

*         .         *         .         *         .         *

     .         .         .         .         .         .

.         *         .         *         .         *         .

     .         .         .         .         .         .

*         .         *         .         *         .         *

Let us call S the set of all those points "+" or "*". Now
consider, for each point in S, the set of points that are
closest to a point x in S than to any other point of S.
(This is the Voronoi diagram of S).  This divides the region
into hexagons as shown in the figure below.  Each oint in
the interior of a hexagon is closet to the center of the
hexagon than to any other point "+" or "*".

There are two types of hexagons: ones whose center is a
landmark ("*") and ones whose center "." is equidistant to
two landmarks. The points in the first type of hexagons are
said to be "clearly closer to a landmark" (the center of the
hexagon), while the points in the other type of hexagon are
said to be "clearly between two landmarks".

.    |    *    |    .    |    *    |    .    |    *    |    .
     +         +         +         +         +         +
   /    \    /    \    /    \    /    \    /    \    /    \
+         +         +         +         +         +         +
|    .    |    .    |    .    |    .    |    .    |    .    |
+         +         +         +         +         +         +
   \    /    \    /    \    /    \    /    \    /    \    /
     +         +         +         +         +         +
*    |    .    |    *    |    .    |    *    |    .    |    *
     +         +         +         +         +         +
   /    \    /    \    /    \    /    \    /    \    /    \
+         +         +         +         +         +         +
|    .    |    .    |    .    |    .    |    .    |    .    |
+         +         +         +         +         +         +
   \    /    \    /    \    /    \    /    \    /    \    /
     +         +         +         +         +         +
.    |    *    |    .    |    *    |    .    |    *    |    .
     +         +         +         +         +         +
   /    \    /    \    /    \    /    \    /    \    /    \
+         +         +         +         +         +         +
|    .    |    .    |    .    |    .    |    .    |    .    |
+         +         +         +         +         +         +
   \    /    \    /    \    /    \    /    \    /    \    /
     +         +         +         +         +         +
*    |    .    |    *    |    .    |    *    |    .    |    *

Now, given a point in the plane choose either the landmark
clearly closest to it or one of the two closest each with
probability 1/2.

There is a variant of this for a square grid (but having up
to 4 "closest landmarks"). It is relatively straight-forward
to give the formulas for the landmarks associated with a
point in the plane. I will expand on this on the following
days.

Ciao, Jorge

---

From: "Richard L. Barnes" <[email-masked]>
Date: Fri, 27 Aug 2010 13:09:44 -0400

Hey Jorge,

I enjoyed your ASCII art, and this is an interesting idea, but seems  
to have a lot more complexity?  Could you clarify what you think the  
benefit of this system is over the one Martin had proposed?  I  
actually think it's quite a bit worse, in that it misses the point of  
Martin's algorithm.

Here's my thinking:

1. There's not really any point to choosing the area returned  
probabilistically, since you can get both areas with repeated  
queries.  You might as well return the union of the two hexagons.

2. There's actually no point to returning the second hexagon either,  
since a moving target will reveal which hexagon he was in.  For  
example, zooming in on the a piece of the lattice, suppose an entity X  
moves as indicated:

   \  A  /
    \   /
     \ /
      +
   X---->X
B    |    C
      |
      +
     / \
    /   \
   /  D  \

At first, the algorithm will return A+B, and afterward, it will return  
A+C, so an observer can deduce that the target has moved from B to C,  
and can discard A as a possible location.

3. Even worse, based on the timing of the change, the observer can  
tell that the target is somewhere near the boundary (H below),  
obviously an area much smaller than A, B, C, or D, much less A+B or A+C.

   \  A  /
    \   /
     \ /
      +
      HX
B    H    C
      H
      +
     / \
    /   \
   /  D  \

This is exactly the problem that Martin's algorithm solves with the  
"hidden trigger" concept.  That feature of the algorithm prevents an  
observer from isolating the target to a boundary, so the problem (3)  
above doesn't arise.

--Richard

On Aug 27, 2010, at 12:08 PM, Jorge Cuellar wrote:

>>> My email was a little loose in its use of language, so I can  
>>> understand how you might have trouble understanding this.
>>>
>>> More inline...
>>>
>>> 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:
>>>>
>>> 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:
>>>>
>>> This is a replacement for the original Javascript code I used to  
>>> describe the algorithm.  The complete (original) is here:
>>>
> [email-masked]

---

From: "Richard L. Barnes" <[email-masked]>
Date: Fri, 27 Aug 2010 13:20:21 -0400

> information away if you did not remember what your last

This doesn't seem like a bad assumption to me.  If the sever is  
already storing policy information for a target, caching a location  
value or a circe is only a very few more bytes.

> something about it? (Most hashes are fine: but hashes of

Good random number generation is actually relatively easy with modern  
crypto libraries.  I don't think this should be a concern.

You can do that with Martin's algorithm, since any location value that  
contains the circle computed with his algorithm can be returned.  The  
location server is free to choose, e.g., circles centered on  
landmarks, as long as these circles are big enough to contain the  
rough location computed according to the algorithm.

> of all locations in a neighborhood).

Given that the location server can make use of landmark-based location  
values, as I describe above, the choice of landmarks seems like an  
implementation detail.  As long as the choice meets the requirement  
that the rough location be covered, it won't have any privacy impact,  
so we don't need to specify it.

--Richard

---

From: Jorge Cuellar <[email-masked]>
Date: Sat, 28 Aug 2010 22:07:35 +0200

Hi Richard,

the problem with the algorithm that Martin proposes is the following:
suppose I go once a week to a certain town, say Berlin to visit
somebody.  I let my location to be know with an uncertainty of 5 kms.
So the algorithm chooses some location within 5 kms (or 10) and says
:"I am within a circle of 5 km (or 10)".  But after 10 times, the 10
different circles it provided intersect in a small region. (Or every
night I go home, or everyday I go to work, etc..)

In my algorithm I am not returning the hexagons.  This part of the
algorithm is only to determine the center (the "landmark"), but the
region provided as location is much larger than the hexagon.  So the
regions intersect (and their intersect is not too small). I hoped this
was clear in my first mail, but probably it was not.  I will have time
again on Monday to discuss that in more detail.

cheers, Jorge

On Fri, Aug 27, 2010 at 7:09 PM, Richard L. Barnes <[email-masked]> wrote:
> Hey Jorge,
>
> I enjoyed your ASCII art, and this is an interesting idea, but seems to have
> a lot more complexity?  Could you clarify what you think the benefit of this
> system is over the one Martin had proposed?  I actually think it's quite a
> bit worse, in that it misses the point of Martin's algorithm.
>
> Here's my thinking:
>
> probabilistically, since you can get both areas with repeated queries.  You
> might as well return the union of the two hexagons.
>
> 2. There's actually no point to returning the second hexagon either, since a
> moving target will reveal which hexagon he was in.  For example, zooming in
> on the a piece of the lattice, suppose an entity X moves as indicated:
>
>  \  A  /
>   \   /
>    \ /
>     +
>  X---->X
> B    |    C
>     |
>     +
>    / \
>   /   \
>  /  D  \
>
> At first, the algorithm will return A+B, and afterward, it will return A+C,
> so an observer can deduce that the target has moved from B to C, and can
> discard A as a possible location.
>
> 3. Even worse, based on the timing of the change, the observer can tell that
> the target is somewhere near the boundary (H below), obviously an area much
> smaller than A, B, C, or D, much less A+B or A+C.
>
>  \  A  /
>   \   /
>    \ /
>     +
>     HX
> B    H    C
>     H
>     +
>    / \
>   /   \
>  /  D  \
>
> This is exactly the problem that Martin's algorithm solves with the "hidden
> trigger" concept.  That feature of the algorithm prevents an observer from
> isolating the target to a boundary, so the problem (3) above doesn't arise.
>
> --Richard
>
>
>>>> My email was a little loose in its use of language, so I can understand
>>>> how you might have trouble understanding this.
>>>>
>>>> More inline...
>>>>
>>>> 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:
>>>>>
>>>> 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:
>>>>>

---

From: Jorge Cuellar <[email-masked]>
Date: Tue, 31 Aug 2010 22:24:59 +0200

Hi Richard and all,

instead of trying to present the whole idea in one piece,
let me discuss the problem in shorter mails.

Today:
1. The Problem to be solved
2. Why there is no perfect solution (and still, ones are better than others)

---
1. The Problem to be solved

A user wants to obscure his location: even if the system
knows his location with great preciseness, the user wants
that his location is presented (to certain users or
applications) as a region with a certain "pretended
uncertainty" or "obscurity distance". Instead of saying
"Peter is in this point", the algorithm should return
"Peter is in this region".

There are two different locations, which are some regions
in space, the original location and the reported one. A
condition we have to meet is that the reported location
must contain the original location.

We will discuss the case of the locations as being circles.
Their radius is the uncertainty associated with them.
	
- The original location can be precise (a circle of radius
  0) or imprecise. Without loss of generality we may assume
  that the original location is precise. (If the requested
  obscurity is smaller than the original uncertainty, we
  must live with the original uncertainty).

- The reported location (which is, if needed, obscured, by
  adding a "pretended uncertainty"). Without loss of
  generality we may assume that the reported location is
  imprecise and has a radius chosen by the user.

Thus we will assume that:

- the original location is a point "o" and

- the reported location is a circle C(r,d) with center "r"
  and radius "d".

Let us call:

  r= reported center
  o= original location (or original center)
  d= reported uncertainty, or "distance"

The difference of the two centers is a vector:

  reported center - original center

that we may call the "shift in reporting". Its length (or
absolute value or norm) can be called "distance to reported
center" and its direction (angle to some "x-axis") the
"direction of the shift".

What we want is an algorithm that given
  o= a precise original location and
  d= a distance
provides a reported location, which is a circle of radius d
around a point
  r= reported center
in such a way that this circle contains the original
location and "leaks as less information about the real
location" as possible.

Thus the algorithm has inputs o and d and produces r.

An initial design would be:
Algo1: choose randomly any point within the distance d from
o and report the circle of the required radius d around this
point. In the moment that the user leaves this region,
choose another r.

---
2. Why there is no perfect solution (and still, ones are better than others)

The algorithm Algo1, when the location changes, leaks a lot
of information about the location of the user. Anyone
observing the reported locations knows that the user has
just left one circle in an arc contained by the new circle.
Thus we know that the user is (or just was) in a "region"
(the arc) of area 0. We say, the algorithm "leaks 0-area"
locations.

In principle, this kind of problem is unavoidable. One
would like to have an algorithm that never discloses that a
user was in an area of size 0 (that is, does not leak
0-area). One would also like not to disclose the velocity
of the movement.

It is impossible to obtain such an algorithm. One reason
why there are no perfect algorithms is because there is
public information about streets, planes, speed limits,
etc.

As to the velocity: suppose I want to hide my location
within 10 miles, but I a moving at 80 mi per hour. If an
observer sees my reported locations, he may, no matter how
I choose the set of reported centers r1, r2, r3, ..., if he
sees enough measurements, he can calculate quite accurately
my (mean) velocity.

Two examples are show that it is impossible not to leak
"0-area" when continuously moving: if my location is
reported to be Paris (+- 100 miles) at 10 am and New York
at 6 pm of the same day (+- 100 miles), then you may
conclude (with a very high probability, and that is what
matters) that at some point of the day I was over the
meridian of Greenwich, which has area 0. Or: if you find my
location to be moving west at roughly 80 mi per hour in an
area where there is only one highway (say, in a country
with speed limit 80 mi per hour), then any algorithm
discloses quite precisely my exact location with any
precision after enough time.

Of course, Algo1 is worse than, say:

Algo2: choose randomly any point r within the distance d
from o and report the circle of the required radius d
around this point. Choose randomly a second radius, the
"trigger radius", a value between 0 and d. In the moment
that the user leaves the "trigger circle", C(r, d1), choose
another r.

This one is better because when the reported location of
the user changes continuously, the algorithm does not leak
0-area by providing those two reported values. (But as
mentioned before, an observer may notice than in a certain
time span the user crossed a border or another region of
area 0).

This algorithm, as many others have a different problem
(which, I think, is worse from the point of view of privacy
than 0-area leakage): suppose I go once a week to a
certain town, to visit somebody, say a friend or a business
partner. (Or every night I go home, or everyday I go to
work, etc..). I let my location to be know with an
uncertainty of, say, 10 miles. So the algorithm chooses
some location r within 10 mi and reports a circle around
this r. But after 20 times, the 20 different circles it
provided intersect in a small region.

Thus observers obtain information about what the user
regularly does. That is bad.

This problem has all algorithms that create a shift in
reporting (recall: the vector vector r - o) randomly every
time.  Of course, the shift in reporting can not be chosen
in a deterministic way, even if the value depends on some
secret of the user (those secrets will leak much to quickly
 fro many reasons.  For instance, the exact location of the
 person can be observed at certain places, etc).
---

ciao,
Jorge

---

From: "Thomson, Martin" <[email-masked]>
Date: Wed, 1 Sep 2010 07:35:12 +0800

This sort of analysis is interesting, but I'm trying to imagine what sort of outcome you're hoping to achieve.

For 2, I'm not yet convinced of the conclusion that there is no perfect solution.  The model is still too loosely defined to make that assessment.  In all cases, there is some information revealed; but the question is to what extent that information can be considered significant.

Now, we could spend a lot of time on this sort of analysis, but that's not helping to address the immediate need for a solution.

From my perspective, and with the work as it is, I'd be more interested in a shooting gallery.  Propose an algorithm.  Describe what information is revealed and under what circumstances and maybe assumptions.  Then we pick one and keep the shortcomings visible.  We could pick more than one and leave it to the policy to dictate which algorithm is applied, but that is far from optimal for many reasons.

--Martin

> Sent: Wednesday, 1 September 2010 6:25 AM
> To: Richard L. Barnes
> Cc: Thomson, Martin; [email-masked]; [email-masked];
> [email-masked]; [email-masked]

---

From: "Thomson, Martin" <[email-masked]>
Date: Wed, 1 Sep 2010 09:16:24 +0800

I'll take a stab at explaining the (current) known weaknesses in the algorithm that I have proposed.  At this stage, I'm not going to propose countermeasures, but there are some possibilities.

==Proposed algorithm

  When providing a new location, randomize the point to expand uncertainty to the required distance.

  Only provide a new location when the centroid of the known location moves outside a trigger circle.

  Trigger circle is defined at the same time as a new location, it has a radius of the required distance and its centre is up to half that distance from the centroid of the known location at that time.

==Weaknesses

(1)
Scenario: 
  The Target visits the same location multiple times over time.  

Assumptions required by recipient: 
  The Target is visiting the same location.

Constraints on scenario:
  Each time, location is only reported while at that location, not on the approach to, or leaving from the location.  This requires that the Target be unable to located on approach to or exodus from the location.  This constraint is met by having the means of location disabled while in transit - e.g. by turning off their phone.

Weakness: 
  Multiple samples can be combined over time to determine the location that is visited.  For example, this might be the location of the Target's home.

(2)
Scenario:
  The algorithm randomly produces two subsequent locations where the two centres of uncertainty are 2.5 times the distance (or approaching that number) apart.

Assumptions required by recipient:
  The recipient must know the obscuring distance; a recipient might be able to assume this value by observing that previous reported locations have the same uncertainty.

Constraints on scenario:
  The obscuring distance must have been revealed previously.  This is possible if the uncertainty of the known location does not exceed the obscuring distance.

  The location must be known with low (or very low) uncertainty at the time that each of the subsequent obscured locations are produced.

  Random chance determines that this scenario is unlikely.

Weakness:
  At the time that the location is produced, the recipient knows that there is a point within the new reported location that is 1.5 times the obscuring distance from a point within the last reported location.  

  Given that the distance between the two locations is such that there is only a small region within each location that meets this constraint, the location of the Target is known with uncertainty approaching that of the known location.

(3)
Scenario:
  Movement.

Assumptions required by recipient:
  Approximately straight line travel over the interval, or

  Travel along an identified route.  Even a relatively large obscuring distance might not prevent a recipient from identifying that the Target is travelling along a particular highway over time.

Constraints on scenario:
  Constant or relatively constant travel speed.

Weakness:
  Average speed of travel can be estimated.  The longer the distance between two locations, the less uncertainty present in the estimate.

  An upper or lower bound on speed might be determined.  If, as in the previous scenario, two locations are produced with significant distance between them, it might be possible place a lower bound on speed over an interval.  From this, it might be possible to identify that the Target is exceeding a speed limit.

  These need not be consecutive reported locations.

There may be other flaws, but these are the ones that I've been able to identify so far.

--Martin