With mobile phones becoming first-class
citizens in the online world, the rich location data they
bring to the table is set to revolutionize all aspects of
online life including content delivery, recommendation
systems, and advertising. However, user-tracking is a
concern with such location-based services, not only because
location data can be linked uniquely to individuals,
but because the low-level nature of current location APIs
and the resulting dependence on the cloud to synthesize
useful representations virtually guarantees such tracking.
In this paper, we propose privacy-preserving locationbased
matching as a fundamental platform primitive and
as an alternative to exposing low-level, latitude-longitude
(lat-long) coordinates to applications. Applications set
rich location-based triggers and have these be fired based
on location updates either from the local device or from a
remote device (e.g., a friend’s phone). Our Koi platform,
comprising a privacy-preserving matching service in the
cloud and a phone-based agent, realizes this primitive
across multiple phone and browser platforms. By masking
low-level lat-long information from applications, Koi
not only avoids leaking privacy-sensitive information,
it also eases the task of programmers by providing a
higher-level abstraction that is easier for applications to
build upon. Koi’s privacy-preserving protocol prevents
the cloud service from tracking users. We verify the
non-tracking properties of Koi using a theorem prover,
illustrate how privacy guarantees can easily be added to
a wide range of location-based applications, and show
that our public deployment is performant, being able to
perform 12K matches per second on a single core.