  A major feature of the emerging geo-social networks is the ability to notify
a user when one of his friends (also called buddies) happens to be
geographically in proximity with the user. This proximity service is usually
offered by the network itself or by a third party service provider (SP) using
location data acquired from the users. This paper provides a rigorous
theoretical and experimental analysis of the existing solutions for the
location privacy problem in proximity services. This is a serious problem for
users who do not trust the SP to handle their location data, and would only
like to release their location information in a generalized form to
participating buddies. The paper presents two new protocols providing complete
privacy with respect to the SP, and controllable privacy with respect to the
buddies. The analytical and experimental analysis of the protocols takes into
account privacy, service precision, and computation and communication costs,
showing the superiority of the new protocols compared to those appeared in the
literature to date. The proposed protocols have also been tested in a full
system implementation of the proximity service.
