Recently, the explosive growth of mobile-connected and location-aware devices enables various proximity services (ProSe). In general, there exist two paradigms enabling the proximity awareness: over-the-top (OTT) and device-to-device (D2D) [1]. In the OTT mode, a centralized server located in the cloud receives periodical location updates from users’ mobile devices (e.g., using GPS). The server then determines proximity based on location updates and interests. However, the constant location updates not only result in significant battery impact because of GPS power consumption and the periodical establishment of cellular connections, but also causes serious privacy problem.