Privacy and security are paramount for the proper deployment of Location-Based Services (LBSs). The authors present a novel protocol based on user collaboration to privately retrieve location-based information from an LBS provider. Their approach neither assumes that users or the LBS can be completely trusted with regard to privacy, nor relies on a trusted third party. In addition, user queries, containing accurate locations, remain unchanged, and the collaborative protocol does not impose any special requirements on the query-response function of the LBS. The protocol is analyzed in terms of privacy, network traffic, and LBS processing overhead.