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.  We propose a distributed approach that integrates nicely with
existing infrastructures for location-based services, as opposed to 
previous work.  Our approach is based on homomorphic encryption and
has several organizations, such as operators of cellphone networks,
collaborate to let a user learn whether k-anonymity holds for her area
without the organizations learning any additional information.  We
also outline several challenges that remain to be addressed