Subject: [Geopriv] Location fuzzing (geolocation policy)

From: Henning Schulzrinne <[email-masked]>
Date: Mon, 9 Jun 2008 09:19:35 -0400

I'm trying to pick up and close the discussion on location fuzzing for  
privacy in the policy draft. I think we agree on the goals:

(1) The circle returned MUST contain the actual location of the target.

(2) In general, no point in the circle must be more likely than others  
to contain the target.

(3) Repeated queries MUST NOT reveal the likely location of the target.

Requirement (3) is new, but it deals with the fact that simple  
randomization will allow an observe to average the values returned and  
get back the real location.

For the moment, I'd like to focus on the simple case that the location  
of the target T is a point P and that the privacy uncertainty should  
be F. The current text in the draft is a bit opaque, so it might help  
to separate the two cases of a point and an uncertainty region.

---

The LS returns a circle with a radius F and a center at a random  
location that contains the point P. For a particular target and  
location, the center of the circle remains the same across queries. An  
LS may store the location of the center or compute it based on a hash  
function that includes the target's identity.

---

Does that work?

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

---

From: Richard Barnes <[email-masked]>
Date: Mon, 09 Jun 2008 09:36:46 -0400

Henning,

I'll confirm that I agree with those goals, and your suggested method 
seems a reasonable way to achieve them.  How do you envision these ideas 
being encoded in the document?  The rules (1) and (3) as normative 
requirements, and the mechanism as non-normative guidance?

Also, let me take a stab at a more general formulation of the mechanism 
you proposed (for a region R):
---

For each target and location, the LS chooses a "baseline circle" with a 
radius F and a center at a random location that contains the region R. 
All responses to queries for this target and location, with an allowed 
radius of at least F, are circles that contain the baseline circle.  For 
example, the LS could keep the center of the circle constant across 
queries and vary the radius of the circle returned.  An LS may store the 
center and radius of the baseline circle or compute it based on a hash
function that includes the target's identity.

---
This includes the point method as a special case, but also provides the 
desired properties for non-point locations.

Cheers,
--Richard

---

From: "Stark, Barbara" <[email-masked]>
Date: Mon, 9 Jun 2008 09:58:13 -0400

Some of the verbiage in this thread worries me a little, so I just want
to be clear about something:

It's ok to fuzz location by providing a civic location without a street
address. That is, by providing city or just the state, or even just the
country.

The response to a query doesn't have to be a geodetic location.

Out of curiosity, why would a fuzzed geodetic location have to be a
circle? Why not a square, or oval, or such?
Barbara 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Richard Barnes
Sent: Monday, June 09, 2008 9:37 AM
To: Henning Schulzrinne
Cc: GEOPRIV WG
Subject: Re: [Geopriv] Location fuzzing (geolocation policy)

Henning,

---

Cheers,
--Richard

*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA622

---

From: Matt Lepinski <[email-masked]>
Date: Mon, 09 Jun 2008 10:12:12 -0400

Barbara,

I believe the context for discussion is the <provide-geo> transformation 
in the geopriv-policy draft. As you've indicated, civic location can be 
fuzzed by removing more specific elements; which makes the 
<provide-civic> transformation easier to specify.

There's no a priori reason that that the fuzzed geodetic location needs 
to be circle. I think the reason to prefer circles is that it makes 
specifying a policy a reasonable task for the user. Currently the schema 
for the <provide-geo> transformation specifies a a single parameter 
which is a radius of uncertainty for the fuzzed location. It seems 
natural for a user to specify 'My co-workers can know my location within 
a mile radius' it seems less natural for a user to specify 'My 
co-workers can know my location to within an ellipse with major axis 2 
miles, minor axis 1 miles, where the major axis is parallel to the equator'.

- Matt Lepinski

Stark, Barbara wrote:

>>(1) The circle returned MUST contain the actual location of the
>>    
>>
>target.
>  
>
>>(3) Repeated queries MUST NOT reveal the likely location of the
>>    
>>
>target.
>  
>

---

From: "Stark, Barbara" <[email-masked]>
Date: Mon, 9 Jun 2008 10:23:43 -0400

Cool. Thanks. That's the answer I was hoping for.
Barbara 

-----Original Message-----
From: Matt Lepinski [mailto:[email-masked]] 
Sent: Monday, June 09, 2008 10:12 AM
To: Stark, Barbara
Cc: Henning Schulzrinne; GEOPRIV WG
Subject: Re: [Geopriv] Location fuzzing (geolocation policy)

Barbara,

a mile radius' it seems less natural for a user to specify 'My 
co-workers can know my location to within an ellipse with major axis 2 
miles, minor axis 1 miles, where the major axis is parallel to the
equator'.

- Matt Lepinski

>The information transmitted is intended only for the person or entity
to which it is addressed and may contain confidential, proprietary,
and/or privileged material. Any review, retransmission, dissemination or
other use of, or taking of any action in reliance upon this information
by persons or entities other than the intended recipient is prohibited.
If you received this in error, please contact the sender and delete the
material from all computers. GA622

*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA623

---

From: Henning Schulzrinne <[email-masked]>
Date: Mon, 9 Jun 2008 10:34:09 -0400

Indeed, this discussion is for geo only (civic got settled long ago);  
the goal is to have something that is reasonably easy to understand  
for users and reasonably hard to screw up for implementors, so that  
users can predict the privacy impact of their rules.

Henning

On Jun 9, 2008, at 10:12 AM, Matt Lepinski wrote:

> Barbara,
>
> I believe the context for discussion is the <provide-geo>  
> transformation in the geopriv-policy draft. As you've indicated,  
> civic location can be fuzzed by removing more specific elements;  
> which makes the <provide-civic> transformation easier to specify.
>
> There's no a priori reason that that the fuzzed geodetic location  
> needs to be circle. I think the reason to prefer circles is that it  
> makes specifying a policy a reasonable task for the user. Currently  
> the schema for the <provide-geo> transformation specifies a a single  
> parameter which is a radius of uncertainty for the fuzzed location.  
> It seems natural for a user to specify 'My co-workers can know my  
> location within a mile radius' it seems less natural for a user to  
> specify 'My co-workers can know my location to within an ellipse  
> with major axis 2 miles, minor axis 1 miles, where the major axis is  
> parallel to the equator'.

---

From: Matt Lepinski <[email-masked]>
Date: Mon, 09 Jun 2008 10:42:20 -0400

I like the idea of specifying the required semantics of the system along 
with a recommended implementation.

However, at the moment I'm uncomfortable with phrases like 'a circle 
with a radius F and a center at a random location that contains the 
point P [or region R]' because I'm not sure that everyone parses these 
words in the same way.

Also, I'm not sure what the units are on the radius F (this doesn't seem 
to be specified in geopriv-policy-15).

In any case, to move the discussion towards recommended implementations, 
I would like to implement Henning's mechanism as follows:
1) Let the point P have coordinates (Px, Py)
2) Randomly select a value X between Px-F and Px+F
3) Randomly select a value Y between Py-F and Py+F
4) Compute the Euclidean distance between (X, Y) and (Px, Py)
5) If this distance is less than F then return the circle of radius F 
with center (X, Y);
else if the distance is greater than F goto Step 2.

Assuming that the units for Px, Py and R are all the same then the above 
procedure selects a circle of radius F uniformly among all circles of 
radius F that contain (X, Y). [As previously discussed, to avoid storing 
a list of previously returned circles, the Location Server could obtain 
random bits by hashing the target's identity, the target's true location 
(and probably a counter of iterations through the loop).] However, if 
the coordinates of P are geodetic and R is a radius in miles things get 
more complicated.

- Matt Lepinski

---

From: "James M. Polk" <[email-masked]>
Date: Mon, 09 Jun 2008 12:45:52 -0500

>you proposed (for a region R):

several questions for this rewrite

>All responses to queries for this target

now we have multiple circles? when did this become art of what 
Henning originally meant?

>and location,

isn't the point that the location is anywhere within 'a' circle, not 
anywhere within s specific circle?

>with an allowed
>radius of at least F,

now you have assigned a minimum radius.  When did that become a 
requirement? and if it is one, what's the maximum size for such a circle?

>  are circles that contain the baseline circle.

what if the target moves outside the original circle, even to the 
point of being farther away then the original F radius away from the 
original circle, how can this "contain the baseline circle"?

>For

---

From: Richard Barnes <[email-masked]>
Date: Mon, 09 Jun 2008 14:48:40 -0400

James,

Picture attached to try to clarify.

> now we have multiple circles? when did this become art of what Henning 
> originally meant?

There's still only one circle that gets returned to the LR.  The 
"baseline circle" is analogous to the random center point that Henning's 
method used.

> anywhere within s specific circle?

That's correct, but moreover, we're trying to make sure that if the LR 
makes multiple queries and takes the intersection, the radius is at most 
F.  Henning's method ma

> requirement? and if it is one, what's the maximum size for such a circle?

There's already a de facto minimum radius in Henning's mechanism -- the 
distance between the center and the true position.

I don't think this is a new requirement, it's something that would come 
out of the policy document.  That is, when the server gets a new policy, 
it finds the minimum radius that anyone is allowed, then sets a baseline 
circle with that radius (in Henning's setup, chooses a point within that 
radius of the true position).

> what if the target moves outside the original circle, even to the point 
> of being farther away then the original F radius away from the original 
> circle, how can this "contain the baseline circle"?

In either scheme, if the target moves more than F away from the original 
center (either the chosen point or the center of the baseline), then the 
LS will have to change the baseline if it wants to provide a radius 
close to F.

--Richard

---

From: Henning Schulzrinne <[email-masked]>
Date: Mon, 9 Jun 2008 15:24:53 -0400

On Jun 9, 2008, at 9:36 AM, Richard Barnes wrote:

> Henning,
>
> I'll confirm that I agree with those goals, and your suggested  
> method seems a reasonable way to achieve them.  How do you envision  
> these ideas being encoded in the document?  The rules (1) and (3) as  
> normative requirements, and the mechanism as non-normative guidance?

Yes, that would work.

>
>
> Also, let me take a stab at a more general formulation of the  
> mechanism you proposed (for a region R):
> ---
>
> For each target and location, the LS chooses a "baseline circle"  
> region R. All responses to queries for this target and location,  
> with an allowed radius of at least F, are circles that contain the  
> baseline circle.  For example, the LS could keep the center of the  
> circle constant across queries and vary the radius of the circle  
> returned.  An LS may store the center and radius of the baseline  
> circle or compute it based on a hash
> This includes the point method as a special case, but also provides  
> the desired properties for non-point locations.

Generally works for me. The second sentence seems a bit convoluted and  
may dilute the requirement.

Any response for that target, location and radius F returns the  
baseline circle.

If the circle just "contains" the baseline circle, it would presumably  
have a larger radius than F, which seems safe, but not what the user  
wanted.

Henning

---

From: Henning Schulzrinne <[email-masked]>
Date: Mon, 9 Jun 2008 15:27:14 -0400

On Jun 9, 2008, at 10:42 AM, Matt Lepinski wrote:

> I like the idea of specifying the required semantics of the system  
> along with a recommended implementation.
>
> point P [or region R]' because I'm not sure that everyone parses  
> these words in the same way.
>
> Also, I'm not sure what the units are on the radius F (this doesn't  
> seem to be specified in geopriv-policy-15).

This would need to be specified; presumably meters.

>
>
> In any case, to move the discussion towards recommended  
> implementations, I would like to implement Henning's mechanism as  
> follows:
> 5) If this distance is less than F then return the circle of radius  
> F with center (X, Y);
> Assuming that the units for Px, Py and R are all the same then the  
> above procedure selects a circle of radius F uniformly among all  
> circles of radius F that contain (X, Y). [As previously discussed,  
> to avoid storing a list of previously returned circles, the Location  
> Server could obtain random bits by hashing the target's identity,  
> the target's true location (and probably a counter of iterations  
> through the loop).] However, if the coordinates of P are geodetic  
> and R is a radius in miles things get more complicated.
>
> - Matt Lepinski
>

---

From: "Thomson, Martin" <[email-masked]>
Date: Mon, 9 Jun 2008 18:59:25 -0500

Richard, Henning,

I like the suggestion (and the requirement).  A few questions:

Can you put your three requirements in the document?  Without these, the
motivation behind the last little bit of Richard's proposed text could
be lost.  On that point, requirement (2) is worded so as to imply
requirements on the generation of the region, more so than how recipient
interpret it.  Perhaps say "the resulting location does not indicate
that any particular point in the provided area is more likely to be
correct than any other."  It's about how a receiver interprets the value
more than how it reflects reality.

Is this radius 'F' the value in the policy document or is it something
else?

What happens if the region R is too large to fit within a circle of
radius F?

Cheers,
Martin

> Sent: Monday, 9 June 2008 11:37 PM
> To: Henning Schulzrinne
> Cc: GEOPRIV WG
mechanism
> This includes the point method as a special case, but also provides
the
> > function that includes the target's identity.

------------------------------------------------------------------------------------------------
This message is for the designated recipient only and may
contain privileged, proprietary, or otherwise private information.  
If you have received it in error, please notify the sender
immediately and delete the original.  Any unauthorized use of
this email is prohibited.
------------------------------------------------------------------------------------------------
[mf2]

---

From: Henning Schulzrinne <[email-masked]>
Date: Mon, 9 Jun 2008 20:36:19 -0400

> Can you put your three requirements in the document?  Without these,  

Yes, I think that will be helpful.

> more than how it reflects reality.

Works for me.

> Is this radius 'F' the value in the policy document or is it something

Yes, it's the "fuzziness" value.

> What happens if the region R is too large to fit within a circle of

This seems somewhat unlikely unless you have either very limited  
privacy expectations or lousy location technology, but it could  
happen. In that case, I'd suggest expanding F to the radius of circle  
that encloses R. That's privacy safe and (mostly, but not completely)  
avoids the averaging problem.

---

From: Richard Barnes <[email-masked]>
Date: Tue, 10 Jun 2008 00:01:29 -0400

> This seems somewhat unlikely unless you have either very limited privacy 
> expectations or lousy location technology, but it could happen. In that 
> case, I'd suggest expanding F to the radius of circle that encloses R. 
> That's privacy safe and (mostly, but not completely) avoids the 
> averaging problem.

I agree; this should be a disallowed case.  Or at least, F should be 
considered a minimum, so that if the LS runs into that case it can 
return a bigger circle.

Of course, that's not what the document actually says right now: Section 
6.5.2 says that if F<R (to abuse notation), then you just return R.
I'm not sure if this meets the privacy goal or not, since you can have a 
region bigger than radius R that has an area less than pi*R^2 (think a 
long, thin rectangle or arc band).

--Richard

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 10 Jun 2008 09:03:17 -0400

The intent is to replace the document text with the results of this on- 
going discussion.

Considering F a minimum seems quite reasonable, as this gives the LS a  
bit more flexibility and may also allow somewhat more efficient  
implementations (such as using a square [in long/lat] instead of a  
circle).

On Jun 10, 2008, at 12:01 AM, Richard Barnes wrote:

>> privacy