Location-based social networks (LBSNs) are convenient, but users must reveal their location information to network servers to enjoy an LBSN's services. However, user location information is sometimes sensitive; its disclosure can potentially cause severe privacy issues, for example, by revealing identity or health information. In this paper, we propose a k-anonymity-based algorithm that preserves user location information. To solve the location-privacy problem, the proposed algorithm, called the dummy-location selection algorithm, generates dummy locations that can be used to hide users’ actual locations. At the same time, because users may want to search through the check-in records of their friends, we design a novel algorithm that enables a quick search either by location or by friends’ social networks. We evaluate the performance of our proposed algorithm via extensive simulations.