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" <jrcuellarj@googlemail.com>
To: "Thomson, Martin" <Martin.Thomson@andrew.com>
Cc: <geopriv@ietf.org>; <rp3@u.washington.edu>; <jmorris@cdt.org>;
<awclark@u.washington.edu>; <alomair@uw.edu>
Sent: Thursday, September 02, 2010 6:28 AM
Subject: Re: [Geopriv] location obscuring
> On Thu, Sep 2, 2010 at 12:31 AM, Thomson, Martin
> <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
>
_______________________________________________
Geopriv mailing list
Geopriv@ietf.org
https://www.ietf.org/mailman/listinfo/geopriv
