AbstractLocation‐based services (LBSs) are emerging fast, and the problems with privacy are growing with them. Although a platform for LBSs can provide the user with high‐quality LBS browsing and powerful mechanisms to reduce the amount of location data transmitted, such a platform is dangerous because it has to manage the location data of the users and the actual service use. This aggregation of private data is a risk in itself. With this paper, we want to show that it is possible to implement most LBSs without such a platform and propose a mechanism enabling fine‐grained control of privacy for an LBS user. We make use of strong cryptographic techniques to enable a real trust relation between individuals and a weaker trust relation between an individual and a company. Copyright © 2011 John Wiley & Sons, Ltd.