A secure location-based alert system with tunable privacy-performance trade-off

Abstract

Monitoring location updates from mobile users has important applications in many areas, ranging from public health (e.g., COVID-19 contact tracing) 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.

Keywords: Location privacy; Searchable encryption.

Fig. 1

Location-based Alert System

Fig. 2

System Model (n = 2, m = 2, d = 8)

Fig. 3

Predicate evaluation on ciphertexts with HVE

Fig. 4

Naive Baseline Encoding

Fig. 5

Hierarchical partitioning on three levels

Fig. 6

Hierarchical encoding and token aggregation

Fig. 7

Token Aggregation: Gray vs hierarchical encoding

Fig. 8

Example of expanding alert zone (in grey) at level k = 0 (a) and k = 1 (b). At level 0, a total of 6 cells (illustrated with stripes) are added to obtain 3 fully-covered areas $R_{[4,5]\times [0,1]}^0$, $R_{[6,7]\times [2,3]}^0$, and $R_{[4,5]\times [4,5]}^0$. At level 1, four additional cells are added to the area $R_{[2,3]\times [0,1]}^1$. The final expanded alert zone contains all cells in $R_{[4,7]\times [0,3]}^0$ and $R_{[4,5]\times [4,5]}^0$ (both grey and diagonally-striped cells in (b))

Fig. 9

a Cell indices within a 2 × 2 patch; b Array marked for a 2 × 2 patch

Fig. 10

Example of candidate patches for an area of size 2 × 2 a Three candidate patches for an area with one zone cell; b One candidate patch for an area with two zone cells; c Two candidate patches for an area with two zone cells; d One candidate patch for an area with three zone cells

Fig. 11

Baseline encoding results

Fig. 12

Hierarchical encoding results on uniform data

Fig. 13

Hierarchical encoding results on Gaussian data

Fig. 14

Gray vs. hierarchical encoding on Gaussian data

Fig. 15

Effect of preprocessing on uniform data

Fig. 16

Hierarchical encoding results for Variable Key Length, Gaussian data

Fig. 17

Parralel results on uniform data

Fig. 18

Parralel results on Gaussian data

Fig. 19

Zone expansion improvement vs alert zone coverage

Fig. 20

Zone expansion improvement vs expansion factor α

Fig. 21

Zone expansion time vs alert zone coverage

Fig. 22

Zone expansion time vs expansion factor α