Subject: Re: [Geopriv] location obscuring

From: Jorge Cuellar <[email-masked]>
Date: Wed, 1 Sep 2010 13:12:50 +0200

Hi Martin,

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

What I am hoping to achieve: an algorithm that does protect
privacy, as good as we get it. I do not want an algorithm
that discloses where I am or what places I visit regularly.
I do think we can have an algorithm that protects privacy
in a better way.

> For 2, I'm not yet convinced of the conclusion that there
> is no perfect solution.

Good! I would like to know about it.

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

OK.  In short it looks like this:

==Proposed algorithm

For a given uncertainty "d" construct a grid of "landmarks"
at roughly distance 1.5d from each other. A "region" is
roughly-a-circle of radius d centered on a landmark. Each
point in space must be at least in one region.

Given a point choose randomly (with equal probabilities or
with a bias towards the prevouly reported location, a
preferred location, or towards closest landmarks) a region
to which this point belongs. But if there are too many
regions to choose from (say, >2, 3 or 4), then choose only
from the 2 (or 3 or 4) regions whose landmarks are closest
to the point.

Any time you move, you can use the same algorithm to
provide a new (or same) region. (But instead of "any time
you move" this can be implemented using a "trigger circle").

That's it!!

You can choose a geodetic grid or a civil one, in the first
case you can choose a triangular or a rectangular grid or
other ones. Most of my past mails was describing in detail
how to construct the girds.

The thing to care about is how to implement the algorithm
efficiently. This was the topic also in my past mails. The
basic idea is simple: The borders of the regions divide the
space into connected components called "blocks": Two points
are in the same block iff they are in exactly the same
regions. We do not want blocks that are too small, nor
points that are in too many regions. We get rid of small
blocks by rearranging the borders of the regions in those
small areas. Thus we are cutting the small blocks into
pieces and lumping them into neighboring blocks that are
larger. In this way, the regions are not perfect circles,
but roughly-a-circle.

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

agree!

==Weaknesses

The information leaked in the algorithm described is at
worst: in which intersection or regions you are moving
around, or are frequently visiting, etc. This is not too
bad as you can choose those intersections to be not too
small.

As to the algorithm you proposed:

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

This is not entirely correct: if you are approaching, say,
every evening your home via the same route, if you report
your location when you are approaching home, you will get a
very close approximation of the route that you are using.

Another question:

If you have several devices providing information: are we
sure all the provided locations are processed by the same
 *instance* of the algorithm (same server, same local data)?

-- Jorge

---

From: Jorge Cuellar <[email-masked]>
Date: Wed, 1 Sep 2010 23:35:54 +0200

Hi Martin,

> As to the algorithm you propose:
>
>> (1)
>> Scenario:

One example:

suppose you regularly fly into a city (Paris, NY, whatever).
The airport is a certain distance, say 10 units, from
downtown, to the east.

Whenever you land you turn on the device that measures your
location. Now you get into a taxi and go to a certain part
of the city, say at most 10 units away from downtown.

Suppose you want an uncertainty of 40 units. You want your
friends to know that you are in this city, but not which of
the 4 companies N, W, S, or E (all 10 units away from
downtown) you are visiting. You may feel quite safe with the
proposed algorithm: you are never 40 units away from the
airport not 40 units away from downtown.

But a friend who sees the information that the algorithm
outputs is able (after a while) to deduce quite easily how
far and in which direction you are travelling in the city.

This is true because if you travel only to a place close to
the airport itself, the algorithm will seldom change the
provided location. But if you travel 10 units west of the
city the algorithm will tend to change location relatively
often. Or 10 units north or 10 units south. And the
eavesdropper can distinguish those three cases rather
rapidly. (In statistical terms: you can test the 4
hypothesis:
a) 10 units north
b) 10 units east
c) 10 units west
d) 10 units south
with a high confidence with a large enough sample).

You can see this effect with a simple simulation:

Take the following 4 points in the plane:

A=(-10,0) (Airport)
N=(0,10)
W=(10,0)
S=(0,-10)
E=(-10,0)

Consider now a movement from A to N. Repeat this 100 times.
For each time, see if the reported location changes in the
path, and if yes, select the last reported location. Take
as "statistic" the average of all those numbers. (If never
the location change your statistic is the average of the
100 reported locations).

Call this number you got (your statistic) N1.
Now repeat the experiment 100 times and obtain numbers N2,
N3, ..., N100.

Now repeat the whole procedure with W, S, and E and compare
the results.  If my intuition is not wrong, you will get 4
clusters of numbers.

Up to this point this may be the simulation your friend
does.

If you now secretly choose one of the 4 (N, W, S, E) and
only disclose the statistic you obtained, the confidence of
your friend identifying which of the 4 cases is happening
is high, by just looking at the clusters.

Another simulation: consider a movement from (0,0) to (x,0)
(say, initially x=20) in the plane and let your algorithm
create a set of reported locations with uncertainty 40.
This average of the last reported locations will provide a
good indication on how large x is.

I can not tell you now how much information the algorithm
is leaking per movement from the airport to N, W, S or E.
But for sure it is not too little. (Look at the
simulations; with different numbers it will be much more).
And this happens everywhere, in every city or every town.

But my point is: you are leaking much more information than
what you could.

>  *instance* of the algorithm (same server, same local data)?

If we can not be sure of this, and two different instances of
the same algorithm are processing information about your
location and providing location according to the same policy,
the situation is much worse.

ciao, Jorge

---

From: "Thomson, Martin" <[email-masked]>
Date: Thu, 2 Sep 2010 06:31:33 +0800

> From: Jorge Cuellar [mailto:[email-masked]]

I'd like a little more precise a definition of this algorithm.  In particular, how the grid point is selected and how an implementation might decide to report a new location.  Some strategies reveal more location than others.  For one, taking movement of the known location as a trigger leads to the same multiple sample problem you are concerned about.

The other concern that I have is regarding falsity.  One of the characteristics of the algorithm I proposed (and those that lead to it) was that the known location was inside the reported region.  This means that the report is never purposefully made false.

Now, if we are willing to accept outright lies, we can probably protect privacy a whole lot better.

...
> very close approximation of the route that you are using.

You are right.  This can be generalized to discovery of a well-travelled route as well as a single location, with all the same constraints.
 
>  *instance* of the algorithm (same server, same local data)?

That's an interesting question.  You mean to say that the state is shared?  That will depend on implementations, and my experience doesn't extend to the sorts of implementations of presence systems that would have this.  Based on the scaling architectures that I am familiar with, it should be possible to ensure that the information is provided by instances that use the same state.  Perhaps we might state that this is a requirement on those implementations.

---

From: Jorge Cuellar <[email-masked]>
Date: Thu, 2 Sep 2010 14:28:51 +0200

> I'd like a little more precise a definition of this
> algorithm. In particular, how the grid point is selected
> and how an implementation might decide to report a new
> location. Some strategies reveal more location than
> others. For one, taking movement of the known location as
> a trigger leads to the same multiple sample problem you
> are concerned about.

OK.  Some details of the algorithm in short are:

We have, given an uncertainty d ("distance"):

G: a "grid" of landmarks

r: landmarks: the centers of "possible reported locations"

C: possible reported locations (=Circle) : all circles of
    radius d around a landmark: C(r,d)

R: Regions: A region is almost the same as circle C=C(r,d)
	  except that (small) pieces of C (around the borders of
	  C) have been "cutted away". Thus they are
	  almost-circles. Note that the regions intersect.

B: Blocks: a block is a convex area (line segments with
    end-points in the block are contained in the block)
    that contain in their interior no border of a region.
    Thus all points in a block belong to exactly the same
    regions. Blocks are disjoint and the union is the whole
    space in question. (They partition the space).

A block B is thus contained in a set of regions C1, C2, ...
with centers r1, r2, ...  We say that the Block is
Near(r1, r2, ..).
[for triangular grids, we will have only one or two
regions].

Below I will tell you how to construct Blocks and then
regions (as unions of blocks).  But first let me explain you
the main idea of the security of the algorithm.

Since the blocks partition the space, at any time you are
in in exactly one block and therefore close to one or to
two landmarks. [This procedure is good for triangular
grids. For rectangular grids you may go up to 4 closest
landmarks. But let us discuss triangular grids as "the one
protocol" I am proposing here.]

You will choose the landmark as one of those one or two
closest. [For more complex grids, you may have more].
Notice that the algorithm for choosing one or the other
landmark does not depend on *where in the block* you are.
Thus, the algorithm will never leak any information about
where in a block you are or have been. I say: "you may be
leaking, in worst case the block".

The mechanism for choosing a landmark (and therefore a
region) like this: if you are in Near(r), close to only one
landmark r, choose it. If not, you are in Near(r1,r2) and
you have exactly two choices (the two closest landmarks, r1
and r2). You choose one non-deterministically (randomly or
with a bias) as follows:
if your previous reported location in one of the two
you may have a bias toward that one,
if you have a "preferred landmark", you may have a bias
towards it.

Blocks are constructed like this

(Version 1):
===========

With a suitable choice of coordinates, the grid points are:

 (e1 x n, e2 x m) (n, and m range over the integers,
                with n+m = even
                e1 and e2 are numbers with
                   e2/e1 =((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,2e2),  (0,4e2),  ...
 (e1,e2),  (e1,3e2),  (e1,5e2),  ...
 (2e1,0), (2e1,2e2), (2e1,4e2), ...
 (3e1,e2), (3e1,3e2), (3e1,5e2), ...

Those points G ("*") are the "landmarks". Also the
midpoints of the sides of the triangles are inserted (shown
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 point 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".

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

(Version 2)
===========

given a point p in the space look at the circles C it
belongs to.

If it belongs only to one circle C=C(r,d), then we say:
"this point is clearly closest to landmark r". The set of
all points close to r is denoted
Near(r).

If it belongs to two circles C(r1,d) and C(r2,d), then:
"this point is clearly between r1 and r2".

If it belongs to more than 2 circles, then choose the two
closest landmarks and we still say: "this point is clearly
between r1 and r2".

The set of all points between r1 and r2 is denoted
Near(r1,r2).

A block is one of two types: it is either the set of points
clearly closest to one landmark r, or the set of points
between neighboring landmarks r1 and r2. (I am disregarding
the points that are in some borders: just consider them to
be on one side or the other). Thus a block is either
Near(r) or Near(r1, r2) (=Near(r2, r1)).

You can visualize the idea quite easily: take a "Venn
Diagram" with 3 circles intersecting all of them.  We do
not like this small little triangle in the middle (the
intersection of all).  We cut it into 3 smaller triangles
and lump those smaller triangles into the three neighboring
intersections of only two sets.  Thus we have three regions
A, B, C and 6 blocks.

What I do not like about this algorithm version is that some
blocks are rather "flat".  Remember: you may be leaking, in
worst case the block.

For both versions again:
=======================

Now regions are constructed like this: the region
corresponding to landmark r is the union of all blocks:
Near(r), Near(r,*).

> The other concern that I have is regarding falsity. One
> of the characteristics of the algorithm I proposed (and
> those that lead to it) was that the known location was
> inside the reported region. This means that the report is
> never purposefully made false.

For me, falsification is not a concern.
In RFC 3693 (Geopriv Requirements) we had:

9.3.  Truth Flag
Geopriv MUST be silent on the truth or lack-of-truth of the location
information contained in the LO.  Thus, the LO MUST NOT provide an
attribute in object saying "I am (or am not) telling you the whole
truth."

I read that as saying that one could lie about the
location.
But I think that this must be a decision of the user.
The algorithm can not *force* users to lie.
And still the algorithm must protect their privacy.

---

From: "Carl Reed" <[email-masked]>
Date: Thu, 2 Sep 2010 10:05:47 -0600

I sent a synopsis of this email discussion on location obscuring to the OGC 
Members.

An interesting response already and one that suggests focusing on use cases 
on a broader basis. I suspect that the US DoD has some interesting 
approaches.

There are interesting variants of this problem in Meteorology - observing 
ships suppressing their location to avoid piracy. This has caused serious 
issues, and our current solutions are not very elegant and incur extra 
expense, such as obscuration and restitution at collecting centres, or 
encryption of marine satellite telecomms traffic.

Weather observations from unknown locations are not very helpful.

Similar problems occur with submarines and fishing vessels (skippers 
obscuring where they, and the fish, are from other skippers)

These could be considered as real world use cases.

Chris

Chris Little
OGC Meteorology & Oceanography Domain Working Group

----- Original Message ----- 
From: "Jorge Cuellar" <[email-masked]>
To: "Thomson, Martin" <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>; <[email-masked]>; 
<[email-masked]>; <[email-masked]>
Sent: Thursday, September 02, 2010 6:28 AM
Subject: Re: [Geopriv] location obscuring

> _______________________________________________
> Geopriv mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/geopriv
>