RE: Location fuzzing

There is an alternative method in:

http://tools.ietf.org/html/draft-thomson-geopriv-uncertainty-03#section-4.4

This discusses a method that could be used to prevent some of the basic attacks on a “fuzzed” location.  It’s basically the same algorithm, but it prevents accidental reveals of location through multiple requests by maintaining a fixed offset at any one location.  There’s a method described for hiding the fixed offset.

From: public-geolocation-request@w3.org [mailto:public-geolocation-request@w3.org] On Behalf Of Richard Barnes
Sent: Sunday, 8 November 2009 9:37 PM
To: public-geolocation@w3.org
Cc: Doug Turner
Subject: Location fuzzing

Hey all,

I got a question from Doug a little while ago about location fuzzing, and thought the whole group might be interested in the response.

The current approach we're taking in GEOPRIV is described in this document:
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21>
Geodetic fuzzing is in Section 6.5.2 ...
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21#section-6.5.2>
... and fuzzing of civic addresses is in Section 6.5.1:
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21#section-6.5.1>

These techniques start from a slightly different place than the W3C Geolocation API:
-- Geodetic location is given by a shape (e.g., point, circle, ellipse, polygon, arc-band), rather than a single point with a radius
-- Civic location is given by an RFC 5139 address structure

The geodetic fuzzing algorithm take two inputs:
1. A shape representing the user's estimated location, and
2. A "fuzzing radius" F in meters
From these, you generate the fuzzed result in the following way:  First, you choose a random "baseline circle" that  (1) has a radius at least F, and (2) covers the input shape (the user's location).  The shape you return is then any shape that contains the baseline circle.  If there are multiple requests for the user's location, then the return shape may be varied (as long as it still contains the baseline circle).  If the user moves outside the baseline circle, then you choose a new random baseline circle.   Example here:
<http://geopriv.dreamhosters.com/fuzz.pdf>

This algorithm guarantees that all an observer gets by averaging/intersecting is the baseline circle, which has the minimum required uncertainty.  If the target is moving, then you can add enough jitter to obscure this to some extent, and you don't run into boundary issues (like you do with "rounding" or "fixed grid" approaches).

This kind of maps on the the "point+uncertainty" construct that's in the current Geolocation API spec, if you make the mental equivalence "point+uncertainty = circle".  In this analogy, the center of the baseline circle is a random fixed offset from the real location, and the returned points will cluster roughly around the baseline circle (with uncertainty values big enough to cover the baseline circle.

The civic fuzzing works by restricting the set of civic address elements that are returned to a predefined set.  The draft defines six levels (full, building, city, region, country, none); for example, the region level includes the "country" element as well as the "A1", "A2", and "A3" hierarchical elements.

Hope this helps,
--Richard