Social networking services are increasingly accessed through mobile devices. This trend has prompted services such as Facebook and Google+ to incorporate location as a de facto feature of user interaction. At the same time, services based on location such as Foursquare and Shopkick are also growing as smartphone market penetration increases. In fact, this growth is happening despite concerns (growing at a similar pace) about security and third-party use of private location information (e.g., for advertising). Nevertheless, service providers have been unwilling to build truly private systems in which they do not have access to location information. In this paper, we describe an architecture and a trial implementation of a privacy-preserving location sharing system called Albatross. The system protects location information from the service provider and yet enables fine-grained location-sharing. One main feature of the system is to protect an individual's social network structure. The pattern of location sharing preferences towards contacts can reveal this structure without any knowledge of the locations themselves. Albatross protects locations sharing preferences through protocol unification and masking. Albatross has been implemented as a standalone solution, but the technology can also be integrated into location-based services to enhance privacy.