To benefit from a location-based service, a person must reveal her
location to the service.  However, knowing the person's location might
allow the service to re-identify the person.  Location privacy based
on $k$-anonymity addresses this threat by cloaking the person's
location such that there are at least $k-1$ other people within the
cloaked area and by revealing only the cloaked area to a
location-based service.  Previous research has explored two ways of
cloaking: First, have a central server that knows everybody's location
determine the cloaked area.  However, this server needs to be trusted
by all users and is a single point of failure.  Second, have users
jointly determine the cloaked area.  However, this approach requires
that all users trust each other, which will likely not hold in
practice.  We propose a distributed approach that does not have these
drawbacks.  Our approach assumes that there are multiple servers, each
deployed by a different organization.  A user's location is known to
only one of the servers (e.g., to her cellphone provider), so there is
no single entity that knows everybody's location. With the help of
cryptography, the servers and a user jointly determine whether the
$k$-anonymity property holds or the user's area, without the servers
learning any additional information, not even whether the property
holds. A user learns whether the $k$-anonymity property is satisfied
and no other information. The evaluation of our sample implementation
shows that our distributed $k$-anonymity protocol is sufficiently fast
to be practical.  Moreover, our protocol integrates well with existing
infrastructures for location-based services, as opposed to the
previous research.