Abstract- Mobile Cloud Computing is today’s emerging technology. Customers enjoy the services and application from this combination of mobile technology and cloud computing. Beside all these benefits it also increases the concerns regarding privacy of users, while interacting with this new paradigm One of the services is Location based services, but to get their required services user has to give his/her current location to the LBS provider that is violation of location privacy of mobile client. Many approaches are in literature for preserve location privacy but some has computation restriction and some suffer from lack of privacy. In this paper we proposed a novel idea that not only efficient in its protocol but also completely preserves the user’s privacy. The result shows that by sharing just service name and a large enough geographic area (e.g. a city) user gets required information from the server by doing little client side processing We perform experiments at client side by developing and testing an android based mobile client application to support our argument.