One document matched: draft-thomson-geopriv-location-obscuring-01.txt
Differences from draft-thomson-geopriv-location-obscuring-00.txt
GEOPRIV M. Thomson
Internet-Draft Andrew Corporation
Intended status: Informational November 11, 2010
Expires: May 15, 2011
A Process for Obscuring Location
draft-thomson-geopriv-location-obscuring-01
Abstract
A method for obscuring location information is described. Both
static and changing location information can be obscured. A single
distance measure is input to the process; this parameter controls the
precision of location information that can be extracted by a
recipient.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 15, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Thomson Expires May 15, 2011 [Page 1]
Internet-Draft Obscuring Location November 2010
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Method Characteristics and Applicability . . . . . . . . . . . 3
3. Obscuring Static Locations . . . . . . . . . . . . . . . . . . 4
3.1. Known Point Locations . . . . . . . . . . . . . . . . . . 5
3.2. Known Locations with Uncertainty . . . . . . . . . . . . . 5
3.3. Selecting a Offset Vector . . . . . . . . . . . . . . . . 6
3.4. Multiple Reported Locations . . . . . . . . . . . . . . . 7
4. Obscuring Changing Locations . . . . . . . . . . . . . . . . . 7
4.1. Update Conditions . . . . . . . . . . . . . . . . . . . . 8
4.1.1. Bad Triggers . . . . . . . . . . . . . . . . . . . . . 8
4.1.2. Hidden Trigger . . . . . . . . . . . . . . . . . . . . 9
4.2. Consecutive Reported Locations . . . . . . . . . . . . . . 10
4.2.1. Reducing Variation between Offset Vectors . . . . . . 11
4.2.2. Trade-off in Reducing Variation . . . . . . . . . . . 11
4.3. Returning to the Same Location . . . . . . . . . . . . . . 12
4.3.1. Positional Stability . . . . . . . . . . . . . . . . . 12
4.3.2. Triggering with Positional Stability . . . . . . . . . 13
4.3.3. Selecting a Grid . . . . . . . . . . . . . . . . . . . 13
4.3.4. Random Grid . . . . . . . . . . . . . . . . . . . . . 14
4.3.5. Linear Interpolation of Random Offsets . . . . . . . . 15
4.3.5.1. Uniformly Distributed Interpolation . . . . . . . 16
4.3.5.2. Applying Uniformly Distributed Interpolation . . . 18
4.3.5.3. Selecting an Appropriate Grid Size . . . . . . . . 18
4.3.6. The Wonky Grid . . . . . . . . . . . . . . . . . . . . 19
4.3.6.1. Wonky Grid Points at the Poles . . . . . . . . . . 20
4.3.6.2. Interpolation About the 180th Meridian . . . . . . 20
4.3.7. Temporal Interpolation . . . . . . . . . . . . . . . . 21
5. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
8. Security Considerations . . . . . . . . . . . . . . . . . . . 22
9. Informative References . . . . . . . . . . . . . . . . . . . . 23
Appendix A. Sample Implementation . . . . . . . . . . . . . . . . 24
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 27
Thomson Expires May 15, 2011 [Page 2]
Internet-Draft Obscuring Location November 2010
1. Introduction
A method for obscuring location information is described. This
method obscures location information such that it can be provided to
recipients without revealing the location of the subject to within
the desired distance.
Obscuring location has applications for protecting privacy, as
described in [I-D.ietf-geopriv-policy].
This method uses a single configuration parameter as input: an
_obscuring distance_.
A location recipient (or recipient) is the entity that is given
location about a target entity. The goal is to ensure that the
recipient is unable to recover location information with better
accuracy than is desired. Despite this obscuring the recipient
should still be able to use the reported locations.
The obscuring process 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_.
2. Method Characteristics and Applicability
The method described here is intended to provide limited protection
for location information by constrained degradation. The method has
the following characteristics:
Simple Configuration: It might be possible to define a more complete
solution for obscuring location information that is more
configurable. However, a more configurable option would also
demand greater involvement from users so that they would be able
to specify a configuration that meets their goals. This method is
designed to be easy to understand, which increases the chances
that a user is able to successfully choose an appropriate
configuration. The method has just one input parameter: the
obscuring distance. A separate parameter for grid size is set by
recommendation.
Irreversible: Obscuring is intended to be irreversible. Information
is lost by applying the process. Multiple applications of this
process to the same input location is could reduce information
more than a single application of the process with the largest
obscuring distance.
Thomson Expires May 15, 2011 [Page 3]
Internet-Draft Obscuring Location November 2010
Increases Uncertainty: A recipient does not need to treat obscured
location information any differently to location information that
contains uncertainty. The uncertainty of the reported location is
increased so that the reported location includes the known
location. Thus, the information that is reported is correct,
though the accuracy might be reduced. This document relies on a
definition of uncertainty for location described in more detail in
[I-D.thomson-geopriv-uncertainty].
Two Dimensions: The method described in this document operates in
two dimensions only. Many of the principles might be applicable
in a higher number of dimensions, though no effort has been made
to validate their integrity. A three-dimensional location can be
reduced to a two-dimensional form for use in this algorithm. This
is not contrary to the goal of reducing the amount of information
provided.
Time Invariant: The method described in this document does not use
time. An entity performing obscuring does not need to consider
time in applying this method. Only the location is protected, not
the time that the location was determined. The time from the
known location is included in the reported location.
Obscuring Distance Not Secret: No attempt is made to protect the
obscuring distance as a secret. It is assumed that a recipient is
able to learn this value.
Minimal State: An entity that performs obscuring of locations often
performs this service for the combination of many targets and
recipients. This process requires only that the obscuring entity
hold maintain a trigger location for each recipient. The
additional state that an obscuring entity retains in order to
apply this obscuring method is a small increment over what is
typically required. The current known location does not need to
be retained; it need only be reacted to when it changes. [TBD:
determine an algorithm that removes the need for retaining the
trigger location; this might be possible.]
3. Obscuring Static Locations
A static location doesn't change. That is, different locations are
not attributed to a single target at different times.
The basic location obscuring case involves a single, isolated
instance of location information.
It might be appropriate to apply just this section in protecting the
Thomson Expires May 15, 2011 [Page 4]
Internet-Draft Obscuring Location November 2010
privacy of a single location. A recipient must be unable to acquire
multiple location instances for the same entity if this is the only
form of obscuring used.
3.1. Known Point Locations
A known point location can be obscured by adding a randomized offset
vector to the location. The size of the offset vector is randomly
selected so that the reported location could be anywhere within the
obscuring distance of the known location, see Section 3.3.
The uncertainty of the reported location is set to the obscuring
distance. This ensures that the reported uncertainty region encloses
the known location.
Note: It's not sufficient to increase the uncertainty region so that
it minimally includes the known location. Doing this reveals that
the known location is at the boundary of the reported uncertainty
region.
3.2. Known Locations with Uncertainty
A known location with uncertainty is reduced to a circular
uncertainty region (see [I-D.thomson-geopriv-uncertainty], Section
4.2). An irregularly shaped uncertainty region is difficult to
evaluate against the scalar obscuring distance, and it might
inadvertently reveal more information than intended.
A known location with uncertainty greater than the obscuring radius
does not require additional obscuring. The radius of the circular
uncertainty region is compared to the obscuring distance to determine
if further obscuring is necessary. A location with sufficient
uncertainty can be directly reported.
Randomization is needed if the known location contains insufficient
uncertainty. As for a point location, an offset vector is added and
the uncertainty increased to the obscuring distance. A smaller
offset vector is necessary where the known location has uncertainty -
this vector need only be of a size up to the obscuring distance, less
the existing uncertainty.
The reported uncertainty is increased so that the reported location
contains an uncertainty radius of at least the obscuring distance.
An uncertainty in a known location cannot be recovered by a recipient
of an obscured location unless it is larger than the obscuring
distance.
Thomson Expires May 15, 2011 [Page 5]
Internet-Draft Obscuring Location November 2010
Paradoxically, more accurate location determination methods are
better suited to obscuring.
A location that is reported with uncertainty does not always have
a uniform probability distribution. A non-uniform distribution is
not conducive to obscuring, since a location with an unevently
distributed probability distribution reveals that the location of
the target is more likely to be in specific parts of the
uncertainty region.
Information on the likely probability distribution cannot be
conveyed in many systems, including presence (see [RFC4119],
[RFC5491]). The location determination method can be reported,
which can reveal characteristics of the probability distribution.
Specific measures to counteract this effect are therefore not
feasible.
Removing or replacing the location determination method parameter
denies a recipient any information about probability distribution.
3.3. Selecting a Offset Vector
To select a random offset vector of up to a given size, select two
uniformly distributed random numbers. The first is used to select a
random angle, the second to select a random distance.
Assuming a "random()" function produces a number distributed between
0 (inclusive) and 1 (exclusive) - that is, the range [0, 1) - the
angle and distance can be produced by the following:
angle = random() * 2 * pi
distance = sqrt(random()) * size
or
distance = (1 - |random() - random()|) * size
...where "sqrt(x)" takes the square root of "x" and "|" takes the
absolute value of the enclosed. "size" is the desired size of the
random vector, which could be the obscuring distance less any
existing uncertainty.
A recipient that is able to learn the state of the random number
generator could use this to determine the known location from a
reported location. A secure random number generator [RFC4086]
provides an assurance that recovering the state of the random number
generator is made more difficult.
Thomson Expires May 15, 2011 [Page 6]
Internet-Draft Obscuring Location November 2010
3.4. Multiple Reported Locations
Multiple applications of this algorithm produce different results.
The intersection of multiple reported locations can be used to
recover a better estimate of the known location. This recovered
estimate has less uncertainty than the obscuring distance, which is
not desirable.
Multiple reported locations for the same known location MUST NOT be
produced. An entity that is responsible for obscuring location might
achieve this by storing the reported location with the obscured
location.
It is possible to implement obscuring for a static location without
retaining state. Seeding a pseudo-random number generator with data
that is not available to the recipient can ensure that the same
result is produced from the same input. Taking a hash of the known
location combined with a secret key ensures that this seed cannot be
easily determined by a recipient. A hash function that includes the
values shown in Section 4.3.4 is sufficient for this task.
4. Obscuring Changing Locations
Applications that use the location of a target over time, such as
presence [RFC4079] require additional steps to ensure that the
location a recipient acquires does not reveal more information than
desired.
The first consideration is the frequency of updates. As the target
moves, the known location changes. A continuous stream of reported
locations could give a recipient sufficient information to determine
the known location with low uncertainty in a fashion close to that
described in Section 3.4.
Note: It is not necessary to ensure that a recipient always has
accurate location information. Early proposed algorithms wrongly
assumed that the reported location was required to cover the known
location at all times. Even in the absence of obscuring, changes
in location result in a recipient having outdated information.
The only necessary constraint is that the location be accurate at
the time that it is reported (or the time associated with that
report).
Thomson Expires May 15, 2011 [Page 7]
Internet-Draft Obscuring Location November 2010
4.1. Update Conditions
To limit the amount of information provided to a recipient, new
reported locations are not generated in response to all changes in
the known location. The trigger for creating a new reported location
can be defined.
Any trigger condition needs to be constructed in a way that does not
reveal information. At the point that a new reported location is
provided to a recipient, the fact that the trigger conditions are met
at that point in time provides the recipient with significant
information that could - if the trigger conditions were poorly
defined - reveal significant information.
The goal is to provide a new reported location when the known
location moves by approximately the obscuring distance. This limits
the information that a recipient has available with similar accuracy
to each individual location.
4.1.1. Bad Triggers
One potential trigger is the movement of the target outside of the
reported uncertainty region. At the point that a new reported
location is generated, a recipient knows that the target is a) at the
boundary of the last uncertainty region, and b) somewhere in the new
uncertainty region. The intersection of these two regions produces
an area that is significantly smaller than desired.
New Reported
Location
..--"""--.. ..--"""--.. /
.-' /=\. `-.
,' ,' \\ `.
/ / \\ \
/ / \\ \
| | || |
| | || |
| | || |
\ \ // /
`. `. // \ .'
`._ `._// \ _.'
/ `--..___..--' `--..__\..--'
Last Reported \
Location Recovered Location
Along Border
Figure 1: Trigger on Leaving the Reported Location
Thomson Expires May 15, 2011 [Page 8]
Internet-Draft Obscuring Location November 2010
Similarly, information is revealed if the trigger is movement based
on the known location. A new reported location might be produced
when the known location moves more than the obscuring distance from
the known location from the last report.
That is, when a new location is reported, the corresponding known
location is saved. A new reported location is determined when the
current known location is more than the obscuring distance from
the saved location.
If the recipient is able to assume that the target is moving in a
straight line, the speed of the target is revealed.
4.1.2. Hidden Trigger
To limit the information that is revealed at the point that a new
reported location is provided, the trigger conditions can be based on
information that is not available to the recipient.
Applying randomization to the trigger reduces the ability of a
recipient to make assertions about the significance of a new reported
location.
A hidden trigger is established using the following process:
o When a new reported location is generated:
1. The centroid of the known location is determined.
2. A random offset vector (Section 3.3) of a maximum size of half
the obscuring distance is determined.
3. The offset vector is added to the centroid and this value is
saved as a trigger point.
o When the known location changes:
1. The centroid of the (new) known location is determined.
2. If this centroid is further than the obscuring distance from
the saved trigger point, a new reported location is generated.
Each new reported location is randomized using the process described
in Section 3.
This algorithm ensures that the centroid of the known location moves
between 0.5 and 1.5 times the obscuring distance before a new
reported location is produced. As a consequence, the uncertainty in
Thomson Expires May 15, 2011 [Page 9]
Internet-Draft Obscuring Location November 2010
the distance moved is equal to the obscuring distance.
4.2. Consecutive Reported Locations
The obscuring method has a weakness that is as a direct consequence
of the triggering conditions. These conditions grant a recipient
this information:
For any two consecutive reported locations there is a pair of
points that are less than 1.5 times the obscuring distance apart,
with one point in the area described by each reported location.
The first point is the known location at the time of the first
reported location; the second point is the known location at the
time of the second reported location.
At the time that a location is reported, the recipient can use this
knowledge to determine that the current location of the target is at
the intersection of the new reported location and a circle with a
radius of 2.5 times the obscuring distance, centered on the last
reported location, as shown in Figure 2
Known location .
is in overlap \
Last \ \ New
,.--"--.. \ \ ,.--"--..
,-' `-. \ |,-' `-.
/ \ \_ + \
| | /| |
| o |<---------->|| o |
| \ | --> 1.5OD \| |
\ \ / + /
`. \ ,' |`. ,'
`-..___,.+' ; `-..___,.-'
\ /
|<------>|<----\->|<------>|<-/---->|<------>|<--...
OD OD \ OD / OD OD
\ ,'
2.5OD \ /
\ _,'
_\/' OD = obscuring
_,,-' distance
Figure 2: Consecutive Reported Locations
Two consecutive reported locations can have their centers up to 3.5
times the obscuring distance apart; making the closest points on each
uncertainty region up to 1.5 times the obscuring distance apart.
When consecutive reported locations are maximally distant, a
Thomson Expires May 15, 2011 [Page 10]
Internet-Draft Obscuring Location November 2010
recipient can recover the location of the target almost perfectly.
This relies on the recipient being able to determine the obscuring
distance. As identified, the obscuring distance is not protected.
4.2.1. Reducing Variation between Offset Vectors
This shortcoming can be addressed by reducing the difference between
the random offset vector added to consecutive reported locations.
The extreme case shown in Figure 2 only arises because the absolute
difference between the randomization vector used for in consecutive
reported locations is twice the obscuring distance. The problem
occurs when the difference between consecutive know locations
approachs 1.5 times the obscuring distance in combination with this
large difference between randomization vectors.
Reducing the amount that a offset vector can change between
consecutive reported locations reduces. If the difference between
offset vectors is constrained then the effect of this problem is
reduced.
Using the same offset vector for all reported locations removes the
problem entirely. However, using the same offset vector increases
the chances of that vector being discovered. For instance, if the
target is following a road, reported locations that have a fixed
offset from the known location will reveal the shape of the road.
From this it is trivial to learn the offset vector and hence all
presence and past locations can be recovered.
Each time a location is randomized, the offset vector used can be the
combination of a new random offset vector and the offset vector that
was last used. The proportion of old and new vectors determines the
trade-off between the probability that a recipient is able to learn a
more accurate location with the probability that a recipient is able
to learn the offset.
4.2.2. Trade-off in Reducing Variation
A small amount of randomness at each stage makes it difficult to
learn the offset vector. A number reported locations are required to
learn the offset vector. Therefore, as long as the offset vector is
able to change significantly over a number of reported locations, the
goal is achieved, Thus, the offset vector need only change a small
amount for each consecutive reported location. This need only make
it difficult to learn the vector and to make learning the vector less
useful if it is revealed.
In turn a smaller change in the offset vector maximizes the worst
Thomson Expires May 15, 2011 [Page 11]
Internet-Draft Obscuring Location November 2010
case area. If the absolute difference in offset vectors is half the
obscuring distance, then there is no gap between consecutive reported
locations and in the worst case the recipient is able to determine
the known location to be within 77 percent of the desired area. This
varies based on "r(diff)", as follows:
a(diff) = ((1.5 + diff)^2 - 5.25) / (2*(1.5 + diff))
r(diff) = acos(a(diff)) + 6.25 * acos((1.5 + diff - a(diff)) / 2.5)
- (1.5 + diff) * sqrt(1 - a(diff)^2)
...where "acos(x)" returns the inverse cosine of "x". This only
produces a result where "diff" is less than 2.
It might be useful in this case to create a offset vector that is no
more than "diff" times the oscuring distance different to the
previous vector. This might be done by taking a weighted average of
the previous vector with a new random offset vector as follows:
o[new] = (o[prev] * (2 - diff) + o[random] * diff) / 2
...where "o[new]" is the new ofset vector, "o[prev]" is the new
previous vector, and "o[random]" is a completely random vector of the
same magnitude.
4.3. Returning to the Same Location
A moving target might return to the same location several times. The
method described thus far produces a different reported location each
time. With some inferences, a recipient that is able to observe
location over time could intersect reported locations to recover
Furthermore, if known locations are not available before and after
leaving the location that is frequently visited, only that location
is obscured. The known location could be readily extracted.
4.3.1. Positional Stability
The key to addressing this flaw is to have the randomization of
offset vectors based on the known location. If the same known
location produced a reported location that was equal or very close to
it each time that the location was obscured, this would address the
problem.
It might be possible to take the coordinates of the known location
and pass them through a cryptographic hash function along with a
secret key. The result bits would be sufficiently random to produce
an offset vector. This would ensure that the exact same location
would produce the same random vector.
Thomson Expires May 15, 2011 [Page 12]
Internet-Draft Obscuring Location November 2010
The drawback of this sort of method is that the location is obscured
inconsistently when even the slightest difference occurs in the known
location. Imprecision in the location determination method used
frequently produces variations in the known location, making this
approach not viable.
The goal is to ensure that two known locations in close proximity
produce a constant (or almost constant) random vector. It is also
desirable that the random vector change as the locations change.
This has the consequence of reducing the difference in randomness
between consecutive reported locations, provided that the random
values do not vary significantly over a distance of 1.5 times the
obscuring distance.
It might be desirable if the random vectors changed over a longer
distance, as Section 4.2.1 demonstrates. If the offset vector
changed over a period of approximately 4 times the randomization
distance, the vector would change by no more than about 3/4 of the
offset distance.
An approach similar to that described in [PERLIN] is used to achieve
a continuously varying random field. In this, randomness is
constrained to a grid of points with interpolation used to determine
values for intervening points.
4.3.2. Triggering with Positional Stability
No specific changes are required for the triggering process, though
this does require that some state be maintained by the entity that
performs obscuring. For a SIP entity that is maintaining a
subscription, this is not expected to be onerous.
The advantage of having a specific trigger for providing a new
reported location is that it reduces the information provided to a
recipient. Providing updates at a higher rate provide a recipient
with additional information that could be used to recover the offset.
4.3.3. Selecting a Grid
In selecting an appropriate grid with two dimensions, the curvature
of the surface of the Earth presents a challenge. The simplest
approach might be to select an origin at latitude 0, longitude 0.
Grid points could be placed at increments based on a constant ratio
between latitude and longitude and distance; for example, 9e-6
degrees per meter assumes a spherical planet of 6366197 meter radius,
which is slightly smaller than the semi-major axis of the ellipsoid
used in most Earth models.
Thomson Expires May 15, 2011 [Page 13]
Internet-Draft Obscuring Location November 2010
Grid intervals can be set to a multiple of the obscuring distance
that ensures that consecutive reported locations have continuously
varying offset vectors. Assuming that linear interpolation is used
in "n" dimensions, a multiple of "m" produces a proportional change
in the offset vector of:
change = (1 - (m - 1.5 * 2^((3 - n)/2)) / m)^n
For a two-dimensional grid with a multiple of "m", the following
equations identify the latitude and longitude of the four nearest
grid points to a given location:
grid = m * obscuring distance * 9e-6
latitude[low] = floor(latitude / grid) * grid
latitude[high] = latitude[low] + grid
longitude[low] = floor(longitude / grid) * grid
longitude[high] = longitude[low] + grid
...where "floor(x)" produces the nearest whole integer that is more
negative than "x".
The shortcoming of a grid of this nature is that changes in longitude
are more rapid as locations get closer to the poles. At
approximately 60 degrees of latitude (North or South), grid intervals
on the East-West direction are twice as frequent as desired. For
this reason, larger intervals between grid points might be chosen for
longitudes.
A solution for this problem is described in Section 4.3.6. An
alternative problem might select a local tangent plane removes the
effect of the curvature of the Earth, though this introduces the
problem of selecting an appropriate tangent plane as locations
change.
In three dimensions, conversion to Earth-centered, Earth-fixed
Cartesian coordinates renders this problem moot.
4.3.4. Random Grid
At each of the points on the grid, a random offset vector is produced
using the method described in Section 3.3. The resulting offset
vectors are interpolated as shown in Figure 3.
Rather than use a random number generator, the random number should
be produced using a cryptographic hash function. The input to this
hash should include:
Thomson Expires May 15, 2011 [Page 14]
Internet-Draft Obscuring Location November 2010
o a random sequence [RFC4086] with the desired entropy that is only
known by the entity that performs the obscuring,
o the identity of the target,
o each individual coordinate of the grid point, and
o as necessary, an identifier for the purposes of the random number:
angle, distance, and (optionally) a second distance, depending on
the method used to generate the random offset vector.
The inclusion of a secret ensures that a recipient is unable to
construct the offset vector. This secret is persistent so that later
applications of the obscuring formula do not produce a different
offset vector for the same location.
Section 3.3 requires that two or three random numbers are produced.
The additional identifier produces additional randomness where
multiple random (or pseudo-random) numbers are required.
Using a hash in this fashion ensures that each target gets a
different set of random offset vectors and that the same grid point
coordinates produce the same result.
Though ordering need only be consistent between consequent
applications of the obscuring algorithm, the following might be used
to produce random bits:
random = H(secret key | target identity | identifier
| grid coordinate | grid coordinate | ...)
...where "|" represents concatenation, including a delimiter as
necessary (that is, to delineate variable length values).
Alternatively, the same sequence could be used to seed a secure
random number generator [RFC4086]. Extracting values in the same
order makes the "identifier" unnecessary.
One consequence of this approach is that changes to the obscuring
distance result in the noise pattern being completely changed. This
can result in the same known location producing a significantly
different reported location before and after the change.
4.3.5. Linear Interpolation of Random Offsets
Once a grid of random offset vectors is established, an offset vector
is calculated based on the centroid of the known location. Figure 3
shows a point at "(x,y)" and the values that are used in the
Thomson Expires May 15, 2011 [Page 15]
Internet-Draft Obscuring Location November 2010
interpolation process.
| |
- ---o------------------------------o---
/| ^ /|
(x1,y2) | | (x2,y2) |
| | (y2-y) |
| (x,y) | |
| \ v |
|<-(x-x1)->X<------(x2-x)----->|
| ^ |
| | (y-y1) |
| v |
- ---o------------------------------o---
/| /|
(x1,y1) | (x2,y1) |
Figure 3: Grid Interpolation
The offset vector at the identified point is produced by taking the
weighted average of the offset vectors. Two weighted averages are
taken between pairs of adjacent grid points along the same axis, then
the weighted average of the two resulting vectors is taken along the
other axis.
The following equations produce an linearly interpolated offset
vector for any point in this grid cell:
tx = (x - x1) / (x2 - x1)
ty = (y - y1) / (y2 - y1)
w1 = o[x1,y1] * (1 - tx) + o[x2,y1] * tx
w2 = o[x1,y1] * (1 - tx) + o[x2,y1] * tx
offset = w1 * (1 - ty) + w2 * ty
...where "o[x1,y1]" is the random offset vector at the grid point
"(x1,y1)".
4.3.5.1. Uniformly Distributed Interpolation
A consequence of performing a weighted average is that the resulting
value is not uniformly distributed. Depending on the weighting
factor (the value "tx" or "ty" in Section 4.3.5), the resulting
probability distribution has a higher probability of producing values
in the middle of the range of possible values.
For example, the probability distribution for a weighted average of
two uniformly distributed random numbers between 0 and 1 is shown in
Figure 4. The figure shows the case where "t" is less than 0.5,
Thomson Expires May 15, 2011 [Page 16]
Internet-Draft Obscuring Location November 2010
though the same distribution is produced for "t" and "(1-t)".
P(x)
|
| ,---------------.
| /: :\
| / : : \
| / : : \
|/ : : \
'----+---------------+------ x
0 t (1-t) 1
Figure 4
In order to correct for this skewing of results toward the middle of
the range, a smoothed interpolation is used.
Over the range from 0 to 1, the following produces a uniformly
distributed interpolation between "a" and "b":
r = a * (1 - t) + b * t
IF r < t AND r < (1 - t) THEN:
r = r * r / 2 / t / (1 - t)
ELSE IF r > t AND r > (1 - t) THEN:
r = 1 - (1 - r) * (1 - r) / t / (1 - t)
ELSE IF t < 0.5 THEN:
r = (2 * r - t) / 2 / (1 - t)
ELSE:
r = (2 * r - 1 + t) / 2 / t
This maps a linearly interpolated value to a smoothed value, using
the cumulative distribution function for the weighted sum of "a" and
"b". This mapping produces a value between 0 and 1 for inputs
between 0 and 1. The mapping is continuous. The mapping is not
monotonically increasing for some values of "a" and "b"; the intent
is to have a uniform distribution between 0 and 1, not between "a"
and "b". Toward the middle of the range, a maximum gradient of 2 is
possible.
For convenience, this interpolation function is represented in
shorthand throughout the remainder of the document:
"uniformDistInterp(a, b, t)".
This has similar characteristics to the smoothing function used in
[PERLIN], except that the goal is not smoothing, but ensuring a
uniform distribution of values in the output. Values are continuous,
but their first derivative is not.
Thomson Expires May 15, 2011 [Page 17]
Internet-Draft Obscuring Location November 2010
4.3.5.2. Applying Uniformly Distributed Interpolation
The method for producing a random vector in Section 3.3 produces a
result that is uniformly distributed in a circular area. As a
result, the cartesian coordinates produced are not evenly distributed
on each axis. Similarly, the polar coordinates have a non-uniformly
distributed magnitude. Rather than interpolate on the output of this
process, the uniformly distributed interpolation is applied to the
random inputs.
Interpolation is performed on a set of random numbers that are
produced at each grid vertex. This is used to produce a single set
of random numbers that are used as input to the algorithm that
produces a random vector.
One consequence of this process is that the angle of the random
vector does not cross 360 degrees (2 times pi) when being
interpolated. In the worst case, interpolation between two points
requires rotation through almost 360 degrees.
The alternative method of interpolating angles - linear
interpolation using the shortest path - does produce an uniformly
distributed output, but it also produces a discontinuity that
could be exploited by a recipient when interpolation is applied in
more than one dimension. It is possible to produce a change in
the offset vector of up to twice the obscuring distance in size as
the known location moves only a short distance.
4.3.5.3. Selecting an Appropriate Grid Size
Assuming the worst case, the maximum rate of change produced by the
uniformly distributed interpolation doubles the rate of rotation. If
the magnitude of the offset vector was the maximum value at each end
of the interpolation, the maximum absolute change in offset vector as
a result of movement is:
diff(m, d) = 4 * sin(d * pi / m)
...where "d" is the distance moved as a proportion of the obscuring
distance, "m" is the number of multiples of the obscuring distance in
each grid interval, and "2 * d < m".
The maximum distance between consecutive updates based on the
triggerring scheme is 1.5 times the obscuring distance. With "d" set
to 1.5, "m" must be set to a value greater than 9 to ensure that the
consecutive offset vectors have an absolute difference of less than
twice the obscuring distance. This protects against the problem
described in Section 4.2.
Thomson Expires May 15, 2011 [Page 18]
Internet-Draft Obscuring Location November 2010
Setting "m" to 20 ensures that this difference is less than one
multiple of the obscuring distance (0.93378 times). This means that
a substantial change in offset vector occurs after linear movement of
20 times the obscuring distance in the aggregate.
4.3.6. The Wonky Grid
To address the concerns caused by the curvature of the Earth, a
modified grid-like structure can be used. It is not strictly
necessary that the grid be absolutely grid-like in structure.
Therefore, it's possible that different grid intervals could be
selected.
This structure uses a different interval for points at different
latitudes, at the selected low latitude:
grid[llat] = grid / cos(latitude[low])
longitude[low,llat] = floor(longitude / grid[llat]) * grid[llat]
longitude[high,llat] = longitude[low,llat] + grid[llat]
...and at the high latitude:
grid[hlat] = grid / cos(latitude[high])
longitude[low,hlat] = floor(longitude / grid[hlat]) * grid[hlat]
longitude[high,hlat] = longitude[low,hlat] + grid[hlat]
...where "cos(x)" produces the cosine of "x".
This produces fewer grid points for latitudes that are further from
the Equator. At the poles (and above), a single offset vector is
sufficient.
Interpolation of these points uses four distinct points, as shown in
Figure 5.
Thomson Expires May 15, 2011 [Page 19]
Internet-Draft Obscuring Location November 2010
(x-x1_2) (x2_2-x)
|<-------->|<----------------->|
| | |
- ---o------------------------------o--- -
/| | ^ |\
(x1_2,y2) : | | : (x2_2,y2)
| | (y2-y)
(x,y) ' |
\ v
X - ------
^
: . : | (y-y1)
| | | v
- ---o---------------------------o--------------- -
/| | |\
(x1_1,y1) |<--------------------->|<->| (x2_1,y1)
(x-x1_1) (x2_1-x)
Figure 5: Wonky Grid Interpolation
Linear interpolation uses the amended equations:
tx_1 = (x - x1_1) / (x2_1 - x1_1)
w1 = uniformDistInterp(r[x1_1,y1], r[x2_1,y1], tx_1)
tx_2 = (x - x1_2) / (x2_2 - x1_2)
w2 = uniformDistInterp(r[x1_2,y2], r[x2_2,y2], tx_2)
Note that this uses the uniformly distributed random values selected
at each grid point, rather than the offset vectors. Each random
value is a uniformly distributed random value in the range [0, 1).
4.3.6.1. Wonky Grid Points at the Poles
At 90 degrees North and South, the cosine used to determine the wonky
grid produces a zero. This produces an undefined grid spacing.
To avoid this problem, produce a single value at each pole: (90, 0)
and (-90, 0). This value replaces "w1" or "w2" in the interpolation
equations. Retaining the same weighting for determining the final
offset is desirable, so that the rate of change is not artificially
increased.
4.3.6.2. Interpolation About the 180th Meridian
At 180 degrees East (or West), longitude values cross from positive
to negative values. This produces a discontinuity in the values
used. This could be exploited to learn when the known location cross
the 180th meridian.
Thomson Expires May 15, 2011 [Page 20]
Internet-Draft Obscuring Location November 2010
180/-180 180/-180
| |
+ve: x1a | x2a x1a | x2a
---o---o--X--------o---o--- ... ---o---o--X--------o---o---
x1b | x2b x1b | x2b
. | . . | .
| | | |
|<------------->| |<------------->|
overlap = grid interval overlap = grid interval
Figure 6: Interpolation About 180 Degrees
This problem might only manifest for one of the two interpolations
performed across changing longitude values in a wonky grid. To
address this, the values produced by the negative and positive
aspects are independently generated, then these values are
interpolated over a span of one grid interval.
For any point within half of one grid interval from the 180th
meridian, this algorithm is used. Perform interpolation using the
selected grid points, then add or subtract 360 degrees from the
original value to get a value that is either more than 180 degrees or
less than -180 degrees. Perform interpolation on this second point.
The two interpolated values are then interpolated using a different
proportion. This interpolation is taken on the overlap interval that
crosses the 180th meridian, as shown in the Figure 6. This
proportion is produced by taking the positive input value (that is,
the longitude value, with 360 degrees added if it is negative) and
applying the following:
grid = m * obscuring distance * 9e-6 / cos(latitude)
IF longitide + grid / 2 > 180 OR longitude - grid / 2 < -180 THEN:
t = ((longitude + 360) % 360 - 180 - grid / 2) / grid
random[o] = uniformDistInterp(random[+ve], random[-ve], t)
ENDIF
...where "%" represents the modulo operation. The final interpolated
value is determined using the uniformly distributed weighted average
method described in Section 4.3.5.1.
4.3.7. Temporal Interpolation
Providing different values over time is difficult to balance against
the need to obscure the same location in the same way. It is
possible to add additional dimensions upon which to interpolate the
offset vector. Adding time as one such dimension would allow the
offset vector to change gradually over time as well as with respect
Thomson Expires May 15, 2011 [Page 21]
Internet-Draft Obscuring Location November 2010
to space.
Although a form of temporal interpolation might allow the obscuring
entity to change the secret key that it maintains, it does not
provide positional stability unless the interpolation is performed
over a significant period. Changing the offset vector applied to the
same location would negate much of the benefit derived from the
algorithm.
5. Examples
TBD
6. Acknowledgements
Thanks go to Robert Sparks for identifying key shortcomings in the
original attempts. Richard Barnes, Jorge Cuellar, Cullen Jennings,
Warren Kumari, and Hannes Tschofenig variously provided input,
feedback, criticisms and insightful ideas.
7. IANA Considerations
This document has no IANA actions.
[RFC Editor: please remove this section prior to publication.]
8. Security Considerations
This document describes a method for obscuring location. An effort
has been made to ensure that reported locations do not reveal any
more information than the input dictates. However, obscuring
location is not a substitute for withholding location information if
the goal is to ensure that a recipient remains ignorant of the known
location. Alternatively, a recipient might be provided with
completely falsified location information.
There is little point in obscuring location when other location-
related information is included in a composite document, like a
presence document [RFC3863]. Removing other information, such as
dynamic location information [RFC5965] is necessary to ensure that
this cannot be used to recover the known location.
A reported location can inadvertently reveal far more information
than intended to a recipient in possession of additional information.
Thomson Expires May 15, 2011 [Page 22]
Internet-Draft Obscuring Location November 2010
A recipient might be able to apply this additional information to
determine the location of the target with less uncertainty than
desired. For instance, a recipient with a map might be able to
identify areas on that map that a target is more likely to be found.
A recipient can combine any additional information with the knowledge
that the reported location is correct at the time it is reported to
recover a better estimate of the known location. Aside from map-
based data, other information that could be used to acquire a more
accurate estimate of the location of a target might include knowledge
of the target's past behavior, personality traits, or aggregated
demographic data. Increasing the obscuring distance might increase
the uncertainty in the location the recipient ultimately recovers.
The complexity involved and the large volume of additional data
involved makes more specific measures difficult.
9. Informative References
[I-D.ietf-geopriv-arch]
Barnes, R., Lepinski, M., Cooper, A., Morris, J.,
Tschofenig, H., and H. Schulzrinne, "An Architecture for
Location and Location Privacy in Internet Applications",
draft-ietf-geopriv-arch-03 (work in progress),
October 2010.
[I-D.ietf-geopriv-policy]
Schulzrinne, H., Tschofenig, H., Morris, J., Cuellar, J.,
and J. Polk, "Geolocation Policy: A Document Format for
Expressing Privacy Preferences for Location Information",
draft-ietf-geopriv-policy-22 (work in progress),
October 2010.
[I-D.thomson-geopriv-uncertainty]
Thomson, M. and J. Winterbottom, "Representation of
Uncertainty and Confidence in PIDF-LO",
draft-thomson-geopriv-uncertainty-05 (work in progress),
May 2010.
[PERLIN] Perlin, K., "An Image Synthesizer", ACM SIGGRAPH Computer
Graphics v.19 n.3, p.287-296, July 1985.
[RFC3863] Sugano, H., Fujimoto, S., Klyne, G., Bateman, A., Carr,
W., and J. Peterson, "Presence Information Data Format
(PIDF)", RFC 3863, August 2004.
[RFC4079] Peterson, J., "A Presence Architecture for the
Distribution of GEOPRIV Location Objects", RFC 4079,
July 2005.
Thomson Expires May 15, 2011 [Page 23]
Internet-Draft Obscuring Location November 2010
[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness
Requirements for Security", BCP 106, RFC 4086, June 2005.
[RFC4119] Peterson, J., "A Presence-based GEOPRIV Location Object
Format", RFC 4119, December 2005.
[RFC5491] Winterbottom, J., Thomson, M., and H. Tschofenig, "GEOPRIV
Presence Information Data Format Location Object (PIDF-LO)
Usage Clarification, Considerations, and Recommendations",
RFC 5491, March 2009.
[RFC5965] Shafranovich, Y., Levine, J., and M. Kucherawy, "An
Extensible Format for Email Feedback Reports", RFC 5965,
August 2010.
Appendix A. Sample Implementation
This javascript implements the obscuring algorithm.
/**
* Location obscurer:
* var f = new GeoShape.Fuzzer(100, secret, target);
* var reported = f.fuzz(known);
* This object retains state.
*/
GeoShape.Fuzzer = function(dist, secret, targetIdentity) {
this.distance = dist;
var key = UTF8(secret).concat( [ 0xff ], UTF8(targetIdentity));
this.random = new GeoShape.UIRandom(key, dist);
this.trigger = null;
this.used = 0;
return this;
};
GeoShape.Fuzzer.prototype = {
/**
* Main obscuring function.
* @param {GeoShape} a shape
* @returns {GeoShape.GeoCircle} a fuzzed circle
*/
fuzz: function(shape) {
var cu = shape.calculateCentroid();
/*
* cu contains two attributes:
* centroid: a WGS84 point uncertainty: a distance in metres
*/
if (!cu.uncertainty) {
cu.uncertainty = 0;
Thomson Expires May 15, 2011 [Page 24]
Internet-Draft Obscuring Location November 2010
}
if (this.hasMoved(cu.centroid)) {
var addunc = Math.max(0, this.distance - cu.uncertainty);
var centre = this.fuzzPoint(cu.centroid, addunc);
var unc = Math.max(cu.uncertainty, this.distance);
this.fuzzed = new GeoShape.GeoCircle(centre, unc);
var td = this.distance / 2;
this.trigger = this.randomize(cu.centroid, td);
this.used = 0;
}
this.used++;
return this.fuzzed;
},
/**
* Determine if the location has moved sufficient distance
* from the trigger to require fuzzing.
*/
hasMoved: function(centroid) {
if (!this.trigger) {
return true;
}
return this.trigger.distanceTo(centroid) > this.distance;
},
/**
* Use a continuously varying random grid to move a point.
*/
fuzzPoint: function(point, dist) {
this.random.reset();
var n = this.random.next(point.latitude, point.longitude);
var d = Math.sqrt(n) * dist;
var a = this.random.next(point.latitude, point.longitude);
return point.movePoint(d, a * 2 * Math.PI);
},
/**
* Move a point randomly (not continuous).
*/
randomize: function(point, dist) {
var d = Math.sqrt(Math.random()) * dist;
var a = Math.random() * 2 * Math.PI;
return point.movePoint(d, a);
}
};
/**
* A uniformly distributed pseudorandom number generator that
* produces the same value for the same key, location and
* grid size.
*
Thomson Expires May 15, 2011 [Page 25]
Internet-Draft Obscuring Location November 2010
* @param key a unique, secret key sequence
* @param gridSize the desired size of the grid, in metres
*/
GeoShape.UIRandom = function(key, gridSize) {
this.prefix = (key instanceof Array) ? key : UTF8(key);
this.prefix.push(0xff);
this.grid = 20 * gridSize * 9e-6;
this.reset();
return this;
};
GeoShape.UIRandom.prototype = {
/**
* Get next pseudorandom value for a latitude and longitude.
*/
next: function(lat, lng) {
var lowlat = Math.floor(lat / this.grid) * this.grid;
var bottom = this.interpLongitude(lowlat, lng);
var top = this.interpLongitude(lowlat + this.grid, lng);
var tlat = (lat - lowlat) / this.grid;
this.rCount++; /* next time produces a different answer */
return this.uniformDistInterp(bottom, top, tlat);
},
reset: function() {
this.rCount = 0;
},
/* Takes a point and produces a "random" value. */
hashRandom: function(lat, lng) {
/* need to fix the lat and lng: 7 decimal places */
var flat = Math.round(lat * 1e7).toString();
var flng = Math.round(lng * 1e7).toString();
var input = this.prefix.concat([ this.rCount ], UTF8(flat),
[ 0xff ], UTF8(flng));
var h = SHA1.hash(input);
var r = 0;
for ( var i = 0; i < h.length; ++i) {
r ^= h[i] << ((i % 4) * 8);
}
/* add 0.5 to deal with sign bit */
return r / Math.pow(2, 32) + 0.5;
},
/* interpolate a and b using t, with a uniform distribution */
uniformDistInterp: function(a, b, t) {
var r = a * (1 - t) + b * t;
if (r < t && r < (1 - t)) {
r = r * r / 2 / t / (1 - t);
} else if (r > t && r > (1 - t)) {
Thomson Expires May 15, 2011 [Page 26]
Internet-Draft Obscuring Location November 2010
r = 1 - (1 - r) * (1 - r) / 2 / t / (1 - t);
} else {
r = 0.5 + (r - 0.5) / Math.max(t, 1 - t);
}
return r;
},
interpLongitude: function(lat, lng) {
if (Math.abs(lat) >= 90) {
return this.hashRandom((lat > 0) ? 90 : -90, lng);
}
var size = this.grid / Math.cos(lat * Math.PI / 180);
if ((lng - size / 2) < -180 || (lng + size / 2) > 180) {
var lngpos = (lng + 360) % 360;
var rpos = this.interpLongSimple(lat, lngpos, size);
var lngneg = lngpos - 360;
var rneg = this.interpLongSimple(lat, lngneg, size);
var t = ((lng + 360) % 360 - 180 - size / 2) / size;
return this.uniformDistInterp(rpos, rneg, t);
}
return this.interpLongSimple(lat, lng, size);
},
interpLongSimple: function(lat, lng, size) {
var lowlng = Math.floor(lng / size) * size;
var rlow = this.hashRandom(lat, lowlng);
var rhigh = this.hashRandom(lat, lowlng + size);
var t = (lng - lowlng) / size;
return this.uniformDistInterp(rlow, rhigh, t);
}
};
Author's Address
Martin Thomson
Andrew Corporation
Andrew Building (39)
Wollongong University Campus
Northfields Avenue
Wollongong, NSW 2522
AU
Phone: +61 2 4221 2915
Email: martin.thomson@andrew.com
Thomson Expires May 15, 2011 [Page 27]
| PAFTECH AB 2003-2026 | 2026-04-23 12:57:46 |