Location-Based Services (LBS) can be accessed from a variety of mobile devices to obtain value added information related to the location of the user. Most of the times, these services are provided by a trusted company (e.g. a telecommunications company). In this paper, the authors propose a novel technique to guarantee the privacy of users of LBS. Their technique consists of several modules, but the highest degree of security is achieved thanks to the use of a public-key privacy homomorphism. Unlike the existing approaches, their proposal does not need any trusted third party to anonymise the users and only makes use of a public-key infrastructure.