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

Date: Tue Aug 31 2010 - 19:35:12 EDT

Date: Tue Aug 31 2010 - 19:35:12 EDT

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

*> -----Original Message-----
*

*> From: Jorge Cuellar [mailto:jrcuellarj@googlemail.com]
*

*> Sent: Wednesday, 1 September 2010 6:25 AM
*

*> To: Richard L. Barnes
*

*> Cc: Thomson, Martin; geopriv@ietf.org; rp3@u.washington.edu;
*

*> awclark@u.washington.edu; alomair@uw.edu
*

*> Subject: Re: [Geopriv] location obscuring
*

*>
*

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

_______________________________________________

Geopriv mailing list

Geopriv@ietf.org

https://www.ietf.org/mailman/listinfo/geopriv

Received on Wed, 1 Sep 2010 07:35:12 +0800

*
This archive was generated by hypermail 2.1.8
: Tue Aug 31 2010 - 19:33:11 EDT
*