Subject: Re: [Geopriv] geopriv-policy algorithm constraints and goals

From: Jorge Cuellar <[email-masked]>
Date: Wed, 4 May 2011 20:19:22 +0200

> I'm not sure that I can map your description of the indistinguishability property onto my mental model, but your description of the "location indistinguishability" and "destination indistinguishability" made sense.
>
> This discussion might make sense as a preface to the discussion on assumptions.  Can I request that you draft a few paragraphs that introduces the subject and how we're planning to apply it?

Sure, I will (by the latest, until the 12th of Mai).

---

From: Hannes Tschofenig <[email-masked]>
Date: Tue, 10 May 2011 05:33:39 +0300

Hi Martin, 

> With the idea that we want -geopriv-policy finished sometime this millennium, here's my first, rough attempt at describing constraints and goals for location obscuring.

We have all contributed our share to the delay. 

> ----
> 
> The purpose of a location obscuring algorithm is to provide a location recipient (LR) with location information of reduced quality.  The intent is to provide an LR with location information that is correct, but insufficient to identify the known location without a chosen amount of uncertainty.
> 
> The obscuring algorithm takes a series of _known locations_, which might have greater accuracy than the recipient is permitted to receive.  The obscuring process produces a series of _reported locations_.
> 
> Algorithm Constraints
> 
> Each algorithm MUST be assigned a label.  This label is used to identify the algorithm.  Algorithm labels are added to the location obscuring algorithm registry (see Section x.x).
> 
I wonder why it is important to indicate that. It would sound that a registry is a super new thing but we are using algorithm registries already forever. 
I would drop this. 

> The algorithm MUST accept known locations with uncertainty and produce reported locations with uncertainty that encloses the known location at that time.  That is, the reported location is no less correct than the known location.

See my other mail. I would at maximum go as far as saying "SHOULD" here. 

> 
> Any obscuring algorithm MUST accept a single input parameter of a distance in meters.  Any other tuning parameters for the algorithm MUST be fixed in the definition of the algorithm.
> 
I am not sure why this is a useful requirement as well. I believe what you really want to express with this requirement is that the algorithm has to be simple to use for the end user. When we came up with the idea that the user would be presenting only a single value (in the form of distance in meters) we thought that this would be simple enough. However, none of us is a user interface expert. Hence, I believe it is not useful to put artificial constraints on the algorithm. Imagine that someone comes up with a super great user interface but unfortunately that algorithm would require more parameters then this should still be allowed. 

> Algorithm Goals
> 
> In assessing any algorithm, the information that a recipient can recover determines how effective that algorithm is.  When a recipient (or adversary) makes assumptions [Duckham05] about the movement of the target, they may be able to recover more information than is intended.
> 
> The assumptions that a recipient is forced to make to recover information determines how effective an algorithm is.  The more assumptions that are necessary, the more difficult it is to reliably recover the known location.  While it cannot be assumed that the complexity of applying multiple assumptions would prevent a recipient from applying those assumptions, the probability that a given set of assumptions is incorrect increases with number.
> 
> The following assumptions are considered important for the development of an algorithm that obscures location.  These assumptions are considered to have a high probability of being correct and are therefore the most important assumptions to protect against.
> 
> Stationary assumption:
> 	An algorithm SHOULD obscure the location of a stationary target.  More specifically, when a target does not move, a location recipient should be unable to determine the known location using only the reported locations that are output from the algorithm.
> 
> Continuous movement assumption:
> 	An algorithm SHOULD obscure the location of a moving target.  More specifically, when a target moves, a location recipient should be unable to determine the known location of the target at any point in time using only the reported locations that are output from the algorithm.

While the adversary will be unable to determine the exact information about the location of the target it will learn that the target moves and in which direction (if we additionally assume that the algorithm does not lie). 
Then, with additional information (which is quite likely to be available) there is information about which path the target may have taken.

> 
> Frequent destination assumption:
> 	An algorithm SHOULD obscure the details of a frequently visited location or path.  For a destination that is regularly visited, the algorithm cannot provide the precise location of the frequented location.
> 
> 	Any description SHOULD indicate whether the algorithm prevents a recipient from identifying whether different reported locations correspond to the same known location, and under what circumstances.  This would permit a recipient to learn that the same location is being visited, even if the identity of that location is obscured.
> 
I am not sure whether I fully understand the purpose of these two requirements. 

If a grid is large enough then there will be no path visible. In the other case it will be. Since the grid is a configurable parameter every algorithm will fail to fulfill this requirement. 

I would exclude these further requirements below from the current discussion. We should only work on these once we get a base algorithm finished. I have my doubt that the industry is asking us to work on these given the deployment status of the location obfuscation today. From your description it seems that they fall under the same category as all other requirements. I disagree with that. This is also a more advanced requirement that should be labelled as a MAY, if at all listed. 

> High accuracy assumption:
> 	An algorithm SHOULD obscure location when the known location has low uncertainty or a high frequency update rate.  A theoretical analysis of the algorithm based on a continuous series of perfect known locations is desirable.
> 

> An algorithm may also provide protection for the speed or velocity of a target.  It is desirable that the precise speed of a target cannot be easily learned.  The following assumptions are also important in assessing an algorithm:
> 
> Constant velocity assumption:
> 	An algorithm SHOULD obscure the speed of a target under the assumption of constant velocity or constant speed along a predefined path (such as a road).
> 

> Other assumptions that a location recipient might use to improve their ability to recover a known location might include: upper and lower bounds to speed or acceleration, constrained movement along specific thoroughfares, or inability to be located in areas that are designated inaccessible.
> 

Ciao
Hannes

> Discussion of any additional assumptions that are either rendered ineffective or especially effective is useful in evaluating an algorithm.
> 
> _______________________________________________
> Geopriv mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/geopriv

---

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 10 May 2011 12:14:52 +0800

Hi Hannes,

On 2011-05-10 at 12:33:39, Hannes Tschofenig wrote:
> > Each algorithm MUST be assigned a label.  This label is used to
> identify the algorithm.  Algorithm labels are added to the location 
> obscuring algorithm registry (see Section x.x).
> >
> I would drop this.

Sure.

> > The algorithm MUST accept known locations with uncertainty and
> produce reported locations with uncertainty that encloses the known 
> location at that time.  That is, the reported location is no less 
> correct than the known location.
> 

In your other mail you say two different things on this topic: 
> I am OK with the statement that the reported location must enclose the known location.

Keeping in mind that the only way to provide any level of assurance that the reported location is "accurate" is to incorporate the uncertainty in the input.

I can handle a "SHOULD" here, but we then need to include some sort of guidance on what that really means with respect to accuracy then.

> > Any obscuring algorithm MUST accept a single input parameter of a
> distance in meters.  Any other tuning parameters for the algorithm 
> MUST be fixed in the definition of the algorithm.
> >
> I am not sure why this is a useful requirement as well. I believe what 
> you really want to express with this requirement is that the algorithm 
> has to be simple to use for the end user. When we came up with the 
> idea that the user would be presenting only a single value (in the 
> form of distance in meters) we thought that this would be simple enough.
> However, none of us is a user interface expert. Hence, I believe it is 
> not useful to put artificial constraints on the algorithm. Imagine 
> that someone comes up with a super great user interface but 
> unfortunately that algorithm would require more parameters then this 
> should still be allowed.

Allowing for other types of parameters will make the construction of the policy more difficult, but I'm not opposed to doing that.  In that respect, it's probably best to each algorithm explicitly define its parameters rather than having discrete labels.  It's harder to build and implement, but we could do that.

> > 	An algorithm SHOULD obscure the location of a moving target.
> More specifically, when a target moves, a location recipient should be 
> unable to determine the known location of the target at any point in 
> time using only the reported locations that are output from the 
> algorithm.
> 
> While the adversary will be unable to determine the exact information 
> about the location of the target it will learn that the target moves 
> and in which direction (if we additionally assume that the algorithm 
> does not lie).
> Then, with additional information (which is quite likely to be
> available) there is information about which path the target may have 
> taken.

It depends on the algorithm as to how much information about movement is revealed.  A coarse estimate of direction (and maybe even speed) might be derived, but that might not directly translate to revealing a path.

With enough additional information, it would be unnecessary to attack the algorithm.  Ultimately, the question is how much information we are allowing an adversary to possess before the algorithm is useless.  So you'll have to be more specific.

> > 	An algorithm SHOULD obscure the details of a frequently visited
> location or path.  For a destination that is regularly visited, the 
> algorithm cannot provide the precise location of the frequented 
> location.
> >
> > 	Any description SHOULD indicate whether the algorithm prevents a
> recipient from identifying whether different reported locations 
> correspond to the same known location, and under what circumstances.
> This would permit a recipient to learn that the same location is being 
> visited, even if the identity of that location is obscured.
> >
> If a grid is large enough then there will be no path visible. In the 
> other case it will be. Since the grid is a configurable parameter 
> every algorithm will fail to fulfill this requirement.
> 
> I would exclude these further requirements below from the current 
> discussion. We should only work on these once we get a base algorithm 
> finished. I have my doubt that the industry is asking us to work on 
> these given the deployment status of the location obfuscation today.
> From your description it seems that they fall under the same category 
> as all other requirements. I disagree with that. This is also a more 
> advanced requirement that should be labelled as a MAY, if at all 
> listed.

These are (an attempt at describing) precisely the problems that Jorge wanted included.  That is, I don't want an adversary to learn where I live based on my obscured location that he receives every evening.

The second part is a corollary to this. That is, I want an adversary to have some uncertainty about whether I'm even going to the same place each evening.  That is, the reported location he got yesterday and the one he gets today should not give the adversary any (significant) indication that they apply to the same known location.

Obviously, the simple algorithm we originally devised (all variants) failed this test.  If you continually returned to the same known location, the reported location was obscured differently each time.  That would allow an adversary to make a simple assumption (that these are really the same place) and recover that location with low uncertainty by intersecting all the reported locations.

--Martin

---

From: Jorge Cuellar <[email-masked]>
Date: Sun, 15 May 2011 17:09:46 +0200

>> This discussion might make sense as a preface to the discussion on assumptions.  Can I request that you draft a few paragraphs that introduces the subject and how we're planning to apply it?
Here are two paragraphs that introduce the "indistinguishability"
notions and how we want to apply them.  Let me know what you think:

Privacy properties (as well as security properties) are related to
notions of "indistinguishability". Given an attacker model, that
describes which information an attacker can access, a system is
privacy preserving (or secure) when the attacker can not recover
precise private information based on the observable information that
he can collect. He can not recover the precise information because he
is unable to distinguish several possible values of that information.
In our case, the attacker observes the results of the location
obscuring algorithm at given moments (for simplicity, we assume that
the attacker can autonomously choose those moments, asking the
location obscuring algorithm: "Where is now the target?"). Besides
this access to the algorithm, he may also have some further
information. The two basic situations are the following two: 1. the
target is in a certain location, at home or work or wherever, and the
attacker knows, for some reason, that "the target is in the same
location as before (or yesterday)" (he knows, "he in at home" or "he
is at work" 2. The target starts a movement (say, a journey) to a
remote location, but the attacker knows where the target started his
journey. In both cases, the attacker can ask "Where is now the
target?" and obtain a response from the obscuring algorithm.

For the first one, we call two points to be "indistinguishable as
locations", if an attacker can not infer from the outputs of the
algorithm any information about which of the two points is the
location of a static target. In particular, if the algorithm provides
the same distribution of responses for the two locations, those
locations are indistinguishable. For the second one, consider the
paths starting at one given point. Two points B1, B2 are
"indistinguishable as destinations" if for any path starting in a
point A and ending in B1 there is a path starting in a point A and
ending in B2, such that the attacker can not infer from the outputs of
the algorithm any information about which of the two paths the target
is travelling and in particular, which destination the target has
eventually arrived to.

---

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 31 May 2011 12:37:44 +0800

I apologize for not getting back to this sooner.  I had planned to spend time in the lead-up to our deadline, but instead find myself struggling to follow the thread.

I had some trouble following the exposition in your text.  I actually found your original explanation clearer.

Here's my explanation:
An algorithm takes sensitive information (the known location) and produces less sensitive information (the reported location).

The goal of the adversary or attacker is to derive information about the known location from the reported location.  In order to do this, the adversary makes assumptions.  

An algorithm that does not force an adversary to make any assumptions to recover the known location cannot be used.

The goal of the obscuring algorithm is to limit the ability of an adversary to recover the known location.  An obscuring algorithm is measured by how effectively it deals with an adversary who makes different assumptions.  Since each assumption an adversary makes has a change of being wrong, better algorithms force an adversary to make a greater number or less reliable assumptions in order to discover the known location.
<<<

You've taken a different approach, namely that of looking to the indistinguishability property for support in analysis.  As I said earlier, that's a useful tool in analyzing the algorithm.  We certainly should analyze from different perspectives.  But I think that your criteria need to be much clearer.

I also think that what you are introducing is a new concept, distinct but related to ciphertext indistinguishability.  In more traditional cryptosystems, the result space is such that for any input, the probability of any value in the result space is equal (assuming a well selected key).  That is, if my cipher produces values in the range from 1 to 10, then without knowing the key, I can't predict the output of the cipher with any better than 10% probability (or negligibly more at best).

Location is different.  For a given input, I can know beforehand the set of possible outputs to the algorithm.  That changes the rules.  You can't apply the ciphertext indistinguishability test directly.  You have to set the preconditions of your test very carefully.  And I don't think that your text does that.

It's also different in the sense that we're not attempting to completely hide information.  A traditional cipher attempts to ensure that the plaintext is practically unrecoverable.  We are attempting something that doesn't have exactly the same properties.  The "ciphertext" resembles the "plaintext" to a certain extent, which is a property a traditional cipher must not exhibit.

I can't think of a way to describe this new concept without starting from first principles.  I tried several ways of defining the concept, but I couldn't come up with anything sufficiently clear.

--Martin

On 2011-05-16 at 01:09:46, Jorge Cuellar wrote:
> >> I'm not sure that I can map your description of the
> indistinguishability property onto my mental model, but your 
> description of the "location indistinguishability" and "destination 
> indistinguishability" made sense.
> >>
> >> This discussion might make sense as a preface to the discussion on
> assumptions.  Can I request that you draft a few paragraphs that 
> introduces the subject and how we're planning to apply it?
> >
> is travelling and in particular, which destination the target has eventually arrived to.