Mobile devices equipped with positioning capabilities can ask location-dependent queries to Location Based Services (LBS). To protect privacy, the user location must not be disclosed. Location Based Services are information services accessible with mobile devices through the mobile network and utilizing the ability to make use of the location of the mobile device. Location-based services offer many opportunities for Business and Social purpose. Information of users can be misused thereby raising the issues of security both for the personal privacy and national security. In such a context, privacy concerns are increasing and call for sophisticated solutions able to guarantee different levels of location privacy to the users.