Thanks to the popularity of mobile devices a large number of location-based services (LBS) have emerged. While a large number of 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-grain access control, and query expressiveness. In this work, to the best of our knowledge, we propose the first privacy-preserving outsourced LBS system supporting continuous access control, multi-location queries, and per-query privacy limit. The proposed framework also supports search by location attributes in addition to locations themselves. We 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.