I'll draft an update once we've had our discussion. For the most part, I've agreed with your comments.
On 2011-07-21 at 14:03:46, Hannes Tschofenig wrote:
> Hi Alissa, Hi Martin,
>
> On Jul 17, 2011, at 10:32 AM, Alissa Cooper wrote:
>
> > We'd like to get draft-ietf-geopriv-policy back to the IESG by the
> end of IETF 81.
> >
> > Upon request from the chairs, Martin Thomson has drafted the text
> below describing (1) the fuzzing algorithm evaluation criteria and (2)
> the performance of one algorithm against these criteria (a simple
> circle-based algorithm). We'd like to know if we have rough consensus
> to incorporate this text into the document so we can send it back to
> the IESG. Please express your opinion to the list by Friday, July 22
> (even if it's just, "yes, incorporate the text").
> >
> > Thanks,
> > Alissa
> >
> > ---------------
> >
> >
> > .h1 Location Obscuring Algorithm
> >
> > 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.
>
> ... but insufficient to determine the more precise location
> information as available to the location server, referred as 'known location'.
OK.
> >
> > 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_.
> >
> > Location changes over time. A number of algorithms for obscuring
> > the location of stationary targets exist
> > [http://portal.acm.org/citation.cfm?id=1770566],
> >
> [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.1678&rep
> > =rep1&type=pdf], but are of questionable value when a target moves.
> >
>
> We don't do us a favor with such a text. We could argue with the
> authors of their proposal on why exactly we find them questionable but
> it does not help our document in any way.
> I would suggest to delete the paragraph. We then also do not have to
> add these new references.
Sure.
> > This section describes the goals for a location obscuring algorithm.
> > The normative "SHOULD" is used to describe goals, since it could be
> > impossible for any single algorithm to address all the described
> > goals. It is expected that some goals are only partially or
> > conditionally achieved by each algorithm.
>
> I would change this paragraph and also the beginning of the next
> section to:
> "
> .h2 Algorithm Goals
>
> This section lists design goals for location obscuring algorithms.
> The algorithm described in this document meets these goals and authors
> of yet-to-be-defined location obscuring algorithms are encouraged to
> consider these design goals as well.
> For convenience reasons we use RFC 2119 language to indicate the
> different levels of importance of the individual design goals.
> It could be impossible for any single algorithm to address all the
> describe goals and certain design goals may only be partially or
> conditionally achieved by a specific algorithm.
> "
>
> I am personally not a huge fan of normative statements about future
> algorithms because it almost sounds like the 'using protocol'
> requirements to me. Often the environment and technology changes and
> so the requirements then tend to be out of sync with what we have written.
> We say that with the using protocol requirements quite nicely and you
> had also objected to some of those. They also looked great at the time
> of writing...
That was the point that I was trying to get to with the "SHOULD" thing. At this stage, we're really just describing a wish-list. Normative language is possibly totally inappropriate in that context.
> > .h2 Algorithm Structure
> >
> > The algorithm SHOULD 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.
> >
> > An obscuring algorithm MUST include a description of the user-
> selected
> > inputs it uses and how those inputs affect output of the algorithm.
> >
> > Usability is an important consideration in selecting which inputs an
> > algorithm uses. A rule maker (RM) needs to be able to quickly and
> > easily comprehend the impact of a choosing any available option.
> >
> > This document describes a single input parameter: a distance in
> > meters. Algorithms that use this parameter ensure that there is at
> > least this much uncertainty in the reported location. Algorithms
> > SHOULD restrict their inputs to this one parameter to aid usability.
> >
> > .h2 Algorithm Assessment
> >
> > The effectiveness of an obscuring algorithm under all circumstances
> > might be imperfect. An assessment of effectiveness helps a rule
> maker
> > decide if an algorithm is appropriate.
>
> ... is appropriate for a specific application usage, context, and
> deployment environment.
Done.
> > An algorithm is measured against its goals. An algorithm that aims
> to
> > convey a chosen amount of uncertainty is only partially effective if
> > there are conditions where a location recipient is able to recover
> > location with less uncertainty. Determining the frequency or
> > probability of these conditions and the degree to which uncertainty
> is
> > reduced is the goal of an assessment.
> >
> > Assessment of an algorithm MUST assume that the location recipient
> > knows the choices made by the rule maker, which includes the details
> > of the algorithm and the selected inputs.
>
> I am not sure I capture the essence of the sentences. Are you trying
> to say that transparency is an important property in the design and
> all parties must have access to the algorithm description so that they
> can make (maybe via a third party) an assessment of the quality of the
> algorithm. If that's the idea I am fully on board with it.
> Transparency is important. (The same holds true for security
> algorithms as well.)
Kerckhoff's Principle. Yes.
> > This section describes one possible framework that aids in assessing
> > algorithms.
> >
> > The goal of the adversary or attacker is to derive information about
> > the known location from the reported location.
> >
> > In order to recover location, an adversary makes assumptions
> > [Duckham05] about the location of the target.
> The adversary makes assumptions about which location. It would only
> see the reported location but most likely the assumptions apply to the
> known location.
Correct. Though I wanted to imply that it's more than the known location that they make assumptions about - it's the "real" location.
> With assumption you are most likely referring to things like that the
> target follows certain landmarks, or so. Right? An example of the type
> of assumptions you have in mind would be useful.
That can be done. "By assuming that the target is on or near a road, the recipient can reduce uncertainty to the area near or around roads."
> I am also not quite sure about the value of the reference. While I had
> read the paper a while ago I am not sure from reading the sentence of
> what specifically you are making the reference to it for.
The reference provides a better description of this. The only real benefit of my crude summary is that it's short.
> > These assumptions are
> > applied to the reported location to produce a recovered location
> > that has lower uncertainty than the reported location.
> >
> > recovered = apply(reported, assumption)
> >
> > where:
> >
> > uncertainty(recovered) <= uncertainty(reported)
> > confidence(recovered) <= confidence(reported)
> >
>
> This sounds nice (for a paper) but in fact it does not add a lot for
> the rest of the writeup. Maybe we could shorten this text by omitting
> that part.
Let's drop it then. It was marginal anyway.
> > The assumptions that a recipient is forced to make to recover
> > information determines how effective an algorithm is.
>
> Wouldn't you also, like in security, consider the amount of reported
> location samples the adversary collected or the computational effort
> he has to make?
> Of course you could call this an "assumption"....
In terms of computation effort, I think that you need to assume that the adversary has considerable, though not infinite computational capacity. On the number of samples, it would be better to assume that the adversary has access to all previous samples and potentially all future samples.
> > An assumption
> > that reduces uncertainty significantly without also reducing
> > confidence provides an adversary with better information about the
> > known location. Less reliable assumptions reduce confidence more
> > significantly than they reduce uncertainty.
> >
> > Multiple assumptions can be applied to progressively refine a
> > recovered location. The more assumptions that are used, the more
> > likely it is that any one assumption is bad. Applying a bad
> > assumption could lead to the recovered location being different to
> the
> > known location. Therefore, each assumption that is applied reduces
> > the adversary's confidence in the recovered location.
> >
> > [[I considered discussing the option of increasing confidence here,
> > which would be possible: using the assumption to confirm something.
> > However, increasing confidence has the same net effect as reducing
> > uncertainty when scaling of uncertainty is considered, so I decided
> to
> > keep things simple ... hah.]]
>
> The last 2 paragraphs sound very theoretical to me and all this talk
> about confidence and so on will not help the reader a lot.
> A designer of a new algorithm will not be provided with enough
> information to develop a better algorithm and an adversary will
> hopefully know more.
> I don't believe we even define "confidence" in the document to begin
> with.
The idea of confidence is probably something that needs to be discussed. I would like to reopen the discussion on whether to adopt -uncertainty at some point. Having a reference like that would be useful in times like this.
> > The goal of the obscuring algorithm is to limit the ability of an
> > adversary to recover location information, even when a number of
> > correct assumptions can be made.
> >
> > .h3 Basic Assumptions
> >
>
> I wouldn't use the term "assumptions" here. We are talking about
> requirements or goals (as it was called in a previous section).
> Additionally, it would be useful to point out that these "requirements"
> are design wishes of the authors for future algorithms.
Basic Goals
> > A location recipient in possession of one or more reported locations
> > SHOULD have no more information about any known location without
> > making any assumptions about the nature of the known location. That
> > is, an algorithm SHOULD NOT reveal any more information than its
> > inputs specify to an adversary that makes no assumptions.
> >
> > 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.
> >
> > For each assumption, the recipient SHOULD be unable to recover the
> > known location with less uncertainty than the reported location when
> > the assumption is correct.
> >
> > Stationary assumption: An algorithm SHOULD obscure the location of a
> > stationary target.
>
> It might be useful to add that the challenge here is that a sequence
> of reported location may allow an adversary to compute the
> intersection and to obtain more information about the known location
> as a consequence.
I considered this, but it felt like it was too specific, and this text is already too long, even with the bits you have already suggested be cut.
> > A location recipient SHOULD be unable to
> > recover the known location by assuming that the target is
> > stationary.
> >
> > Continuous movement assumption: An algorithm SHOULD obscure the
> > location of a moving target. A location recipient SHOULD be
> > unable to recover the known location by assuming that the target
> > is moving at a constant speed or with a constraint on
> > acceleration.
> >
> > The description of the algorithm SHOULD include information on
> > what is revealed about a moving target. This includes direction
> > of movement, speed and acceleration.
> >
> > Same place assumption: An algorithm SHOULD obscure the details of a
> > frequently visited place. A location recipient SHOULD be unable
> > to recover the location of the target by assuming that they are
> > the same place as was in a previous reported location.
> >
> > Same course assumption: As for the frequently visited destination,
> > but for a path that the target follows.
> >
> > The description of the algorithm 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: A location recipient SHOULD be unable to
> > recover the known location by assuming that the known location has
> > low uncertainty or is updated frequently.
> >
> > An 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.
>
> s/may/MAY.
Ack.
> >
> > .h3 Additional Assumptions
...Goals.
> > Discussion of any additional assumptions that are either rendered
> > ineffective or especially effective is useful in evaluating an
> > algorithm.
> >
> > The following assumptions depend on the location recipient having
> > additional information, such as topological or demographic data
> > available.
> >
> > Constrained movement assumption: A location recipient MAY be
> > unable to recover the known location by assuming that the target
> > is unable (or less likely) to be located in certain locations.
> >
> > For instance, a location recipient might assume that the target
> > is more likely to be found on a road or footpath. Similarly, by
> > assuming that the target is unlikely be found in a body of
> > water, the known location could be recovered.
> >
> > A more sophisticated assumption of constrained movement uses
> > knowledge of how different locations are connected. An
> > adversary could know that to transit between two points is only
> > possible by following a small set of paths.
> >
> > Goal driven movement assumption: A location recipient MAY be
> > unable to recover the known location by assuming that the
> > movement of the target is driven by a desire to move from one
> > place to another. By using information on relative frequency of
> > different paths, a particular path might be selected with higher
> > probability based on the reported locations.
> >
> > Behavioral or past history assumption: A location recipient MAY be
> > unable to recover the known location by assuming that the target
> > is following pre-established patterns of behavior. These
> > patterns could be derived either from past knowledge of the
> > target, or demographic data that might be refined based on other
> > knowledge about the target.
> >
> > Addressing these additional assumptions is desirable, but
> > potentially difficult. Integrating additional data increases
> > algorithm
> complexity
> > and data might not be available to all implementations.
> >
>
> Will look at the algorithm writeup soon.
>
> Ciao
> Hannes
>
>
> _______________________________________________
> 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
