Private Proximity Detection for Convex Polygons

Proximity detection is an emerging technology in Geo-Social Networks that notifies mobile users when they are in proximity. Nevertheless, users may be unwilling to participate in such applications if they are required to disclose their exact locations to a centralized server and/or their social friends. To this end, private proximity detection protocols allow any two parties to test for proximity while maintaining their locations secret. In particular, a private proximity detection query returns only a boolean result to the querier and, in addition, it guarantees that no party can derive any information regarding the other party’s location. However, most of the existing protocols rely on simple grid decompositions of the space and assume that two users are in proximity when they are located inside the same grid cell. In this paper, we extend the notion of private proximity detection, and propose a novel approach that allows a mobile user to define an arbitrary convex polygon on the map and test whether his friends are located therein. Our solution employs a secure two-party computation protocol and is provably secure. We implemented our method on handheld devices and illustrate its efficiency in terms of both computational and communication costs.