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

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 12 Apr 2011 09:23:45 +0800

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.

I'd sorely like to add additional goals that rely on topology, routing, or behavioral information.  But, I'm afraid that we'll never get an algorithm deployed based on something that complex.  All current indications are that such a method is necessary, but more research is necessary before anything concrete could be proposed.

--Martin

----

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).

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.

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.

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.

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.

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.

Discussion of any additional assumptions that are either rendered ineffective or especially effective is useful in evaluating an algorithm.

---

From: Jorge Cuellar <[email-masked]>
Date: Thu, 14 Apr 2011 21:34:02 +0200

Thanks Martin for the input.  I would add to stationary and frequent
destination:

> 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.
In particular, the algorithm SHOULD obscure the location even if
the attacker knows the details of the protocol and is able to
simulate it.

> 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.
In particular if the attacker knows the details of the protocol
and is able to simulate it.

And also I would add a new assumption:

Indistinguishability assumption:

We call two points "indistinguishable as locations" for an
algorithm, 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 response for two locations,
those locations are indistinguishable. Similarly two points
are called "indistinguishable as destinations" if an attacker
can not infer from the outputs of the algorithm any
information about which of the two points was the
destination of a moving target. This is true in particular,
if every path that ends in one of the two points can be
extended to a path ending on the other point, without
changing the outputs of the algorithm.

Two points are in the same indistinguishability region if
and only if they are indistinguishable as locations and
destinations. An algorithm SHOULD provide a description of
the indistinguishability regions it defines. A theoretical
analysis of the size and shape of the indistinguishability
regions of the algorithm is desirable.

-- Jorge

On Tue, Apr 12, 2011 at 3:23 AM, Thomson, Martin
<[email-masked]> wrote:
> _______________________________________________
> Geopriv mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/geopriv
>

---

From: "Thomson, Martin" <[email-masked]>
Date: Fri, 15 Apr 2011 07:16:10 +0800

On 2011-04-15 at 05:34:02, Jorge Cuellar wrote:
> > 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.
> In particular, the algorithm SHOULD obscure the location even if the 
> attacker knows the details of the protocol and is able to simulate it.

That's a more general constraint.  As a general rule, security by obscurity doesn't work.  I don't see that this is any different.

If you think that the text is useful, I'd add it as a later note.
 
> > 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.
> In particular if the attacker knows the details of the protocol and is 
> able to simulate it.
> 
> We call two points "indistinguishable as locations" for an algorithm, 
> 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 response for 
> two locations, those locations are indistinguishable. Similarly two 
> points are called "indistinguishable as destinations" if an attacker 
> can not infer from the outputs of the algorithm any information about 
> which of the two points was the destination of a moving target. This 
> is true in particular, if every path that ends in one of the two 
> points can be extended to a path ending on the other point, without 
> Two points are in the same indistinguishability region if and only if 
> they are indistinguishable as locations and destinations. An algorithm 
> SHOULD provide a description of the indistinguishability regions it 
> defines. A theoretical analysis of the size and shape of the 
> indistinguishability regions of the algorithm is desirable.

That's a more verbose version of what I intended with the second paragraph.  What you have described is something that is part of the solution space more than the goals.  I considered having an additional assumption for indistinguishable locations, but it's not really related to an assumption that an recipient makes, more just a product of the algorithm.

> > 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.
> >
> > I'd sorely like to add additional goals that rely on topology,
> routing, or behavioral information.  But, I'm afraid that we'll never 
> get an algorithm deployed based on something that complex.  All 
> current indications are that such a method is necessary, but more 
> research is necessary before anything concrete could be proposed.
> >
> > --Martin
> >
> > ----
> >
> > 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).
> >
> > 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.
> >
> > 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.
> >
> > 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.
> >
> >        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.
> >
> >        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.
> >
> 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.
> >
> >        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:
> >
> >        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.
> >
> > Discussion of any additional assumptions that are either rendered
> ineffective or especially effective is useful in evaluating an 
> algorithm.
> >

---

From: Jorge Cuellar <[email-masked]>
Date: Sat, 16 Apr 2011 08:35:47 +0200

> That's a more general constraint. As a general rule, security by
> obscurity doesn't work. I don't see that this is any different.

I think, it only makes explicit something that is
already included.

> If you think that the text is useful, I'd add it as a later note.

I think it is useful.  What would be a "later" note?

> > indistinguishability regions of the algorithm is desirable.

Up to jere it is only a definition: any protocol defines an
indistinguishability region, there is no way to avoid it.
(But perhaps, it is not trivial to calculate what is the
indistinguishability region for a given algorithm). It is
close to well known notions of indistinguishability, like
http://en.wikipedia.org/wiki/Ciphertext_indistinguishability
or, even more, the one used in information flow, see for instance:
http://www.cse.chalmers.se/~andrei/jsac.pdf
So this is not solution space.

> That's a more verbose version of what I intended with the second
> paragraph. What you have described is something that is part of
> the solution space more than the goals. I considered having an
> additional assumption for indistinguishable locations, but it's
> not really related to an assumption that an recipient makes, more
> just a product of the algorithm.

And this last part is the requirement.  It is not solution
space, it just says that the attacker should gain as little
as possible information from the outputs of the algorithm.

-Jorge

---

From: "Thomson, Martin" <[email-masked]>
Date: Mon, 18 Apr 2011 13:47:34 +0800

> I think it is useful.  What would be a "later" note?

Something attached to introductory or explanatory text, rather than a specific point in the discussion.  For instance,

   Keeping the details of an algorithm secret does not serve any useful purpose.  At best, it means that there is another secret that you need to maintain.  At worst, it denies you the expertise of other interested individuals with skills that might otherwise be applied to strengthening the algorithm.

> indistinguishability region for a given algorithm). It is close to 
> well known notions of indistinguishability, like 

The indistinguishability property might be generalized as: given a set of N (chosen) plaintexts T[1], ...T[N], then any ciphertext from the set produced by the algorithm E(T[x]) cannot be identified as being produced by any of the set of plaintexts with a probability greater than 1/N.

There's two ways this principle is being applied.  The most important is where the plaintext is the location of a target as a function of time.  That is T is the location of the Target as it varies over time.  Addressing this form of indistinguishability has to be the primary goal.

You are talking about a second case where each discrete location for the same target is treated as a separate plaintext.

The point under debate is not indistinguishability, but whether this property forms part of the attack options we wish to address (the "assumptions").  Indistinguishability is a tool for analyzing an algorithm, but not part of the set of attacks.  Thus, neither part of the solution space or the set of goals, but a framework for understanding if we've achieved our goals.

If you are looking for an assumption, then we're still talking about the "frequent destination" or "same location" assumption.  That is, the attacker assumes that the known location is the same as the known location that was previously acquired.  The question of how much information the attacker gains when making this assumption is a matter for the analysis of the algorithm.

Incidentally, there's another assumption that's important in analyzing the algorithm that I proposed:

Discrete location assumption:
	An algorithm SHOULD protect a discrete location that is remote from adjacent known locations.  This assumption might be useful to an adversary if the location of the Target is known only at discrete points without known locations in between.  For example, a person that disables location tracking in transit between two points might only have known locations at either end of the journey.

> > paragraph. What you have described is something that is part of the 
> > solution space more than the goals. I considered having an 
> > additional assumption for indistinguishable locations, but it's not 
> > really related to an assumption that an recipient makes, more just a 
> > product of the algorithm.
> 
> And this last part is the requirement.  It is not solution space, it 
> just says that the attacker should gain as little as possible 
> information from the outputs of the algorithm.

Goal.  Let us not place constraints that we cannot provably meet.

> -Jorge

As an aside, in relation to this work, I've been acutely aware of the effect of "Schneier's Law":  <http://www.schneier.com/crypto-gram-1104.html#10>.

---

From: Jorge Cuellar <[email-masked]>
Date: Fri, 22 Apr 2011 11:23:55 +0200

>Something attached to introductory or explanatory text,
>rather than a specific point in the discussion. For
>instance,

Fine.

>> Up to jere it is only a definition: any protocol defines
>> an indistinguishability region, there is no way to avoid
>> it. (But perhaps, it is not trivial to calculate what is
>> the indistinguishability region for a given algorithm).
>> It is close to well known notions of
>> indistinguishability, like
>> or, even more, the one used in information flow, see for
>> instance: http://www.cse.chalmers.se/~andrei/jsac.pdf So
>> this is not solution space.

> The indistinguishability property might be generalized as:
> given a set of N (chosen) plaintexts T[1], ...T[N], then
> any ciphertext from the set produced by the algorithm
> E(T[x]) cannot be identified as being produced by any of
> the set of plaintexts with a probability greater than 1/N.

This is not a generalization (If T[i], T[j] are
indistinguisable, for all i,j, then T[1], ...T[N] are
indistinguishable in the sense you mention.

> There's two ways this principle is being applied. The most
> important is where the plaintext is the location of a
> target as a function of time. That is T is the location of
> the Target as it varies over time. Addressing this form of
> indistinguishability has to be the primary goal.

If you think of T(t) as the continous path, and you are
looking at the values O(T(t)) of obscured locations
(assuming that the algorithm is active each instant of
time), then you get unrealistic versions of
inditinguishability.

> You are talking about a second case where each discrete
> location for the same target is treated as a separate
> plaintext.

Not exactly.  Let me rephrase:

We have high sensitive information (the real location ofr
locations of the target) and low sensitive information (the
obscured location, which is the output of the algorithm).
The "attacker" is simply anyone who is trying to deduce
information about the real location of the target based on the
outputs of the algorithm and perhaps some further information
about the past real locations of the target. We have a notion of
two points being "indistinguishable as locations"
and "indistinguishable as destinations".

For the first one, assume a static (i.e: not moving) target. We
call two points "indistinguishable as locations" for an
algorithm, 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.

> The point under debate is not indistinguishability, but
> whether this property forms part of the attack options we
> wish to address (the "assumptions"). Indistinguishability
> is a tool for analyzing an algorithm, but not part of the
> set of attacks. Thus, neither part of the solution space or
> the set of goals, but a framework for understanding if
> we've achieved our goals.

Just as ciphertext_indistinguishability is the corect concept for
anylyzing if aen encryption algorithm is ok, I think the
indistinguishability of locations is the correct concept here. It
creally relates to the possibilities of attackers learning
infromation from obscured locations.

> If you are looking for an assumption, then we're still
> talking about the "frequent destination" or "same location"
> assumption. That is, the attacker assumes that the known
> location is the same as the known location that was
> previously acquired. The question of how much information
> the attacker gains when making this assumption is a matter
> for the analysis of the algorithm.

> Incidentally, there's another assumption that's important
> in analyzing the algorithm that I proposed:

> Discrete location assumption: An algorithm SHOULD protect a
> discrete location that is remote from adjacent known
> locations. This assumption might be useful to an adversary
> if the location of the Target is known only at discrete
> points without known locations in between. For example, a
> person that disables location tracking in transit between
> two points might only have known locations at either end of
> the journey.

It looks good, but did not understand it fully: How far
is "remote"? What is an "adjacent known location"?  If the
location of a target is known at discrete points, then the
locations visited in the meantime should also be protected,
you mean something like that?

> Goal. Let us not place constraints that we cannot provably

I agree. I think indistinguishability (as stated above) is
achievable.

> As an aside, in relation to this work, I've been acutely
> aware of the effect of "Schneier's Law":
> <http://www.schneier.com/crypto-gram-1104.html#10>.
Me too.

---

From: "Thomson, Martin" <[email-masked]>
Date: Thu, 28 Apr 2011 13:44:45 +0800

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?

On 2011-04-22 at 19:23:55, Jorge Cuellar wrote:
> > Discrete location assumption: An algorithm SHOULD protect a discrete 
> > location that is remote from adjacent known locations. This
> assumption
> > might be useful to an adversary if the location of the Target is
> known
> > only at discrete points without known locations in between. For 
> > example, a person that disables location tracking in transit between 
> > two points might only have known locations at either end of the 
> > journey.
> 
> It looks good, but did not understand it fully: How far is "remote"?
> What is an "adjacent known location"?  If the location of a target is 
> known at discrete points, then the locations visited in the meantime 
> should also be protected, you mean something like that?

Yeah, that text doesn't read so well to me either.  It might be necessary to handle contiguous and non-contiguous paths in some other part of the discussion.

--Martin