| Abstract | In the last decade, location information became
easily obtainable using off-the-shelf mobile devices.
This gave a momentum to developing Location Based Services (LBSs)
such as location proximity detection, which can be used to find
friends or taxis nearby. LBSs can, however, be easily misused to
track users, which draws attention to the need of protecting
privacy of these users.
In this work, we address this issue by designing, implementing,
and evaluating multiple algorithms for Privacy-Preserving
Location Proximity (PPLP) that are based on different secure
computation protocols. Our PPLP protocols support both circle and
polygon range queries and have runtimes from a few to some
hundreds of milliseconds and bandwidth requirements from a few
hundreds of bytes to one megabyte. Consequently, they are
well-suited for different scenarios and offer faster runtimes and
savings in bandwidth and computational power as well as security
improvements compared to previous PPLP schemes. In addition, the
computationally most expensive parts of the PPLP computation can
be precomputed in our protocols, such that the input-dependent
online phase runs in just a few milliseconds. |
|---|
