Privacy and security are paramount for the proper deployment of location-based services (LBSs). We present a novel protocol based on user collaboration to privately retrieve location-based information from an LBS provider. Our 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. We show that our proposal provides exponential scalability in the probability of guaranteed privacy breach, at the expense of a linear relative network cost.