Outsourcing MPC Precomputation for Location Privacy

By Ivan Oleynikov, Elena Pagnin, Andrei Sabelfeld.

Proximity testing is at the core of several Location-Based Services (LBS) offered by, e.g., Uber, Facebook, and BlaBlaCar, as it determines closeness to a target. Unfortunately, modern LBS demand not only that clients disclose their locations in plain, but also to trust that the services will not abuse this information. These requirements are unfounded as there are ways to perform proximity testing without revealing one’s location.

We propose POLAR, a protocol that implements privacy-preserving proximity testing for LBS. POLAR is suitable for clients running mobile devices, and relies on a careful combination of three well-established multiparty computation protocols and lightweight cryptography. A point of originality is the inclusion of two servers into the proximity testing. The servers may aid multiple pairs of clients and contribute towards enhancing privacy, improving efficiency, and reducing the running time of clients’ procedures.

EuroS&P Location Privacy Workshop 2022 paper version: polar-lpw-2022.pdf

Benchmarking source code: polar.tar.gz