A friend locator is a location-based service that is used to detect proximity of when two users are within a user defined distance of each other. When such a service is to be developed for mobile users, two main topics needs to be taken into account. First of all, privacy is a very essential element. The users must not risk revealing personal information about their locations and whereabouts. Second, communication costs is still a very essential topic, when considering mobile devices connected to the Internet. To meet these two general requirements, this paper presents a peer-to-peer location-based service, that is optimized both for privacy and for minimizing communication costs. Three main techniques are employed to reach this goal, namely cloaked regions, dynamic shifted circles and secure multi-party computations. This has ended up with a solution, where a user only communicates with the friends it wishes to detect proximity with, and all a user knows about a friend is, how for away the friend is, with some degree of imprecision. The user does not know in which direction the friend is located, thus it is hard to guess where the friend is located. To reduce communication costs, buffer zones for each user is generated, that allow the user to move freely around within this zone without having to perform any location updates. The solution is flexible, due to proximity distance and precision can be adjusted for each pair of friends. The design has been implemented in a prototype, and tests have been performed to show that it is communicational wise effective.