Mobile application users want to consume location-based services without disclosing their locations and data owners (DO) want to provide different levels of service based on consumer classifications, sometimes without disclosing areas of interest (AOI) locations to all users. Both actors want to leverage location-based services utility without sacrificing privacy. We propose a protocol that supports queries from different classifications of users, such as subscribers/non-subscribers, or internal/external personnel, and imposes embedded fine-grained access control without disclosing user or DO location information. We use Ciphertext Policy Attribute-Based Encryption (CP-ABE) and Hidden Vector Encryption (HVE) to provide flexible access control and mutually private proximity detection (MPPD). Our protocol minimizes expensive cryptographic operations through the use of location mapping with compressed Gray codes, each representing multiple locations. Our protocol encrypts AOI locations using HVE, and then encrypts AOI information using CP-ABE with an expressive access policy. Our protocol’s use of these two encryption methods allows DOs to define a single set of AOIs that can be accessed by sets of users, each with potentially different access permissions. A separate service provider (SP) processes queries without divulging location information of the user or any DO provided AOI.