˲ Determine subscriber location to the desired level of granularity; and

˲ Use a database to map the location to the desired information (such as directions to an espresso shop).

Separating these functions clarifies the anonymity problem while opening up the range of available anonymity-preserving techniques. We begin by determining subscriber location. The best means for preserving anonymity is to do an independent GPS fix on a cellphone. The handset may thus acquire an accurate location estimate without releasing any information to the outside world. This is a general theme; the more that can be done within the handset and kept within the handset, the greater the preservation of anonymity.

However, this approach can be slow. If the handset is to download all necessary SV location information from the SVs themselves, the user may have to wait as long as 12. 5 minutes, a potentially excruciating delay when one needs caffeine. If the process is to be sped up through provision of constellation information by the cellular service provider, some location information must be leaked to that provider. However, such data can be coarse; the network must know only the cell site that is serving the user to provide the data for SVs that are potentially visible to the handset. Such coarse location information provides relatively little information about the user’s beliefs and preferences. Or to use the language of this article’s unicity distance analysis, the preference mapping F operating on cell-site information will produce a preference vector with a large number of erased coordinates.

Khoshgozaran and Shahabi17 suggested another approach to determining location anonymously: use the network to determine the location fix while preventing the network from knowing the subscriber’s actual location. The mobile device biases the data used for the location fix by applying a randomly selected transform to the mobile’s measurements. When the mobile receives the resulting location fix from the network, it removes the effects of the bias by adjusting the fix accordingly.

It follows from these options that

using access-point
and cell-site
location information,
service providers
are able to obtain
location estimates
with address-level
precision.

obtaining a location fix of the desired granularity on the handset need not reduce the user’s location privacy. However, the second piece of LBS, the mapping function, creates two significant obstacles to maintaining privacy, with the second posing a potential personal security concern:

Consistent input granularity. The mapping function requires input granularity consistent with the inherent granularity of the query; a user who wants directions to the nearest espresso shop needs directions, beginning with a position with street-level resolution; and

Known location. Many if not most LBS queries involve objects of known, fixed location; for example, a bookstore has a known location and is generally not in motion. A request for directions indicates the requesting cellphone user will probably be at the location sometime soon.

The following paragraphs consider
general means for accomplishing the
mapping function while retaining a
measure of anonymity:
A release of data is said to provide
k-anonymity protection “…if the infor-
mation for each person contained in
the release cannot be distinguished
from at least k– 1 individuals whose
information also appears in the re-
lease.” 25 It seems logical that such
protection can be obtained for the
LBS mapping function by stripping
identifying information from k LBS
requests, bundling and submiting
them all at once. The LBS server then
provides a combined response from
which individual users are able to ex-
tract information responsive to their
specific requests.

But who or what bundles the original k requests? Gruteser and Grunwald14 suggested a trusted server that bundles and forwards requests on behalf of users, while Ghinita et al. 13 suggested a tamper-proof device on the frontend of an untrusted server that combines queries based on location. However, such approaches fall short of k-anonymity in that there may be side information (such as home location or a known place of business) that would allow the server to disaggregate one or more users from the bundled request. For example, I benefit little from a bundled request if the request