Thanks to the popularity of mobile devices numerous location-based services (LBS) have emerged. While several privacy-preserving solutions for LBS have been proposed, most of these solutions do not consider the fact that LBS are typically cloud-based nowadays. Outsourcing data and computation to the cloud raises a number of significant challenges related to data confidentiality, user identity and query privacy, fine-grained access control, and query expressiveness. In this work, we propose a privacy-preserving framework for outsourcing LBS to the cloud. The framework supports multi-location queries with fine-grained access control, and search by location attributes, while providing semantic security. In particular, the framework implements a new model that allows the user to govern the trade-off between precision and privacy on a dynamic per-query basis.We also provide a security analysis to show that the proposed scheme preserves privacy in the presence of different threats. We also show the viability of our proposed solution and scalability with the number of locations through an experimental evaluation, using a real-life OpenStreetMap dataset.