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 for 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.