TL;DR
This paper introduces a novel privacy-preserving system for friend locator applications that balances strong privacy guarantees with high efficiency and accuracy. It achieves this through a two-phase approach: an initial coarse-grained location filtering using multi-level grids and differential permutation, followed by a fine-grained phase that uses convex polygon decomposition to represent areas of interest, even for irregular shapes.
What Problem Does This Paper Address?
Online social networks increasingly offer "friend locator" features, allowing users to be notified when their friends are nearby. However, these services pose a significant privacy challenge: users must disclose their precise location to a central server, which could potentially reveal sensitive personal information. Existing privacy solutions for general location-based services (LBS) often fall short for friend locators because they either sacrifice accuracy, are inefficient, or cannot handle complex, irregular areas of interest. Furthermore, many solutions fail to protect user privacy when the server and other users collaborate to de-anonymize individuals. This paper aims to address these limitations by providing a system that offers robust privacy, efficiency, accuracy, and flexibility, even under collaborative attacks.
Methods
The proposed system, the Privacy Preserving Algorithm (PPA), operates in two phases:
- Phase One: Quadtree Based Multi-Level Splitting: This phase reduces the computational overhead by coarsely estimating proximity. Users represent their location using a multi-level grid (Quadtree) and a variable-length bit sequence. The length of this sequence is user-defined, allowing them to control their privacy level (longer sequences mean more privacy but less frequent checks). To enhance efficiency and privacy, a "differential permutation" method is introduced. Instead of each user encrypting their location bit sequence for every friend, they encrypt it with their own secret key. The server then uses a pre-shared "difference" between friends' keys to compare these encrypted sequences, avoiding the need for individual encryption per friend. Entropy-based splitting is also employed, dividing the map based on population density rather than just geographical size, which increases uncertainty and thus privacy.
- Phase Two: Privacy and Polygon Decomposition: After phase one filters out most non-nearby friends, this phase handles the fine-grained proximity check. The active user defines their "area of interest" using a set of convex polygons. This is a significant improvement over methods that rely solely on Euclidean distance, as it can accurately represent complex, irregular shapes like those found in a shopping mall floor plan. The privacy mechanism leverages linear operations on these polygon representations. By transforming the area of interest and location data using a secret matrix
H, the system allows the server to perform comparisons without learning the original sensitive information. Crucially, to prevent collusion between the server and other users, a secure multi-party computation-inspired technique is used, where only partial information is exchanged between users and the server, making it impossible to reconstruct individual locations.
Datasets
The paper uses data from the "MilanoByNight simulation" by Every Ware Laboratory from the University of degli Studi di Milan, Italy. This dataset represents the movements of 100,000 users in Milan over a weekend night, with locations sampled every 20 seconds. The total map size is 174 square miles, with an average density of 572 users/mile².
Key Insights and Ideas
- Dual-Resolution Approach is Key: Splitting the problem into a coarse (fast, less private) and a fine (slower, more private) phase dramatically reduces overall communication overhead.
- Population Density for Privacy: Dividing geographical areas based on population density, rather than uniform grid sizes, significantly increases uncertainty and thus privacy. This is a counter-intuitive but powerful insight.
- Convex Polygons for Flexible Areas: Representing areas of interest as convex polygons (or unions thereof) offers superior accuracy and flexibility compared to simple Euclidean distance, especially for real-world, irregular shapes.
- Differential Permutation for Efficiency: This technique cleverly reduces the communication burden on users by allowing them to encrypt their location once with their own key, rather than for each individual friend.
- Mitigating Collusion: The system's design, particularly in phase two, actively addresses the threat of the server collaborating with other users to de-anonymize individuals, a common weakness in other LBS privacy solutions.
Key Results
- Reduced Communication Overhead: Simulations show that the two-phase approach significantly reduces communication overhead for active users, especially when they have a large number of friends. For example, even with 500 friends, the number of nearby friends to check in phase two is typically less than 5.
- Improved Accuracy: The polygon decomposition method demonstrates substantial accuracy improvements over Euclidean distance-based methods, particularly for irregular areas of interest. The enhancement increases with the size of the area of interest and friend density, eventually stabilizing.
- Enhanced Privacy: The system provides strong privacy guarantees, even when the server and other users collaborate. Numerical analysis and simulations suggest that the proposed entropy-based splitting and differential permutation methods contribute to this.
Limitations and Future Work
- Authentication Assumption: The paper assumes users are authenticated by a third party, and it does not focus on preventing spoofing attacks.
- Computational Overhead: While efficiency is improved, the paper acknowledges that some methods, like secure multi-party computation, can still be computationally intensive, though their approach aims to mitigate this.
- Degenerate Polygons: The paper mentions that their method can detect attacks using degenerate polygons, implying that such attacks are a potential concern that their algorithm addresses.
- Future Work: The authors suggest that further work could explore more efficient methods for solving the secure multi-party computation aspects and potentially extend the privacy guarantees to other LBS scenarios. The paper also hints at an integer programming formulation for optimizing the trade-off between grid level and communication overhead.
Summary updated