<Martin.Thomson@andrew.com> wrote:
>> From: Jorge Cuellar [mailto:jrcuellarj@googlemail.com]
>> 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").
> 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.
_______________________________________________
Geopriv mailing list
Geopriv@ietf.org
https://www.ietf.org/mailman/listinfo/geopriv
