  Monitoring location updates from mobile users has important applications in
many areas, ranging from public safety and national security to social networks
and advertising. However, sensitive information can be derived from movement
patterns, thus protecting the privacy of mobile users is a major concern. Users
may only be willing to disclose their locations when some condition is met, for
instance in proximity of a disaster area or an event of interest. Currently,
such functionality can be achieved using searchable encryption. Such
cryptographic primitives provide provable guarantees for privacy, and allow
decryption only when the location satisfies some predicate. Nevertheless, they
rely on expensive pairing-based cryptography (PBC), of which direct application
to the domain of location updates leads to impractical solutions. We propose
secure and efficient techniques for private processing of location updates that
complement the use of PBC and lead to significant gains in performance by
reducing the amount of required pairing operations. We implement two
optimizations that further improve performance: materialization of results to
expensive mathematical operations, and parallelization. We also propose an
heuristic that brings down the computational overhead through enlarging an
alert zone by a small factor (given as system parameter), therefore trading off
a small and controlled amount of privacy for significant performance gains.
Extensive experimental results show that the proposed techniques significantly
improve performance compared to the baseline, and reduce the searchable
encryption overhead to a level that is practical in a computing environment
with reasonable resources, such as the cloud.
