Privé: Anonymous Location-Based Queries in Distributed Mobile Systems 1 National University of Singapore

PRIVÉ: Anonymous Location-Based Queries in Distributed Mobile Systems

• 1 National University of Singapore

• {ghinitag,kalnis}@comp.nus.edu.sg

• 2 University of Peloponnese, Greece

• [e-mail]

Location-Based Services (LBS)

• LBS users

• Mobile devices with GPS capabilities
• Spatial database queries

• Queries

• NN and Range Queries
• Location server is
• NOT trusted

Problem Statement

• Queries may disclose sensitive information

• Query through anonymous web surfing service

• But user location may disclose identity

• Triangulation of device signal
• Publicly available databases
• Physical surveillance

• How to preserve query source anonymity?

• Even when exact user locations are known

Solution Overview

• Anonymizing Spatial Region (ASR)

• Identification probability ≤ 1/K

Central Anonymizer Architecture

• Intermediate tier between users and LBS

PRIVÉ Architecture

K-Anonymity*

K-Anonymity*

Relational and Spatial Anonymity

Redundant Queries

• Send K-1 redundant queries

• Gives away exact location of users
• Potentially high overhead

CloakP2P [Chow06]

• Find K-1 NN of query source

• Source likely to be closest to ASR center

• Vulnerable to “center-of-ASR” attack

QuadASR[Gru03, Mok06]

• Quad-tree based

• Fails to preserve anonymity for outliers
• Unnecessarily large ASR size

Reciprocity

• Consider querying user uq and ASR Aq

• Let ASq = {set of users enclosed by Aq}

• Aq has the reciprocity property iff

• |AS| ≥ K
•  ui,uj  AS, ui  ASj  uj  ASi

hilbASR

• Based on Hilbert space-filling curve

• index users by Hilbert value of location
• partition Hilbert sequence into “K-buckets”

Advantages of hilbASR

• Guarantees source privacy

• K-ASRs have the “reciprocity” property

• Reduced ASR size

• Hilbert ordering preserves locality well
• K-ASR includes exactly K users (in most cases)

• Efficient ASR assembly and user relocation

• Balanced, annotated index tree
• User relocation, ASR assembly in O(log #users)

hilbASR with Annotated Index

PRIVÉ Characteristics

• P2P overlay network

• Resembles annotated B+-tree
• Hierarchical clustering architecture
• Bounded cluster size [,3)

Relocation

PRIVÉ Protocol

• Users self-organize into clusters

• Bounded cluster size [,3)
• Cluster head handles operations
• State replicated at each cluster peer

• Operations

• Join/Departure
• Similar to B-tree insert/delete
• Relocation
• Handled bottom-up, restrict propagation
• K-request
• Decentralized implementation of hilbASR

Operation Complexity

Load Balancing

• Hierarchical architecture

• Inherent imbalance in peer load

• Cluster head rotation mechanism

• Rotation triggered by load
• Communication cost predominant

Fault Tolerance

• Soft-state mechanism

• Cluster membership periodically updated
• Recovery facilitated by state replication

• Leader election protocol

• In case of cluster head failure

Experimental Setup

• San Francisco Bay Area road network

• Network-based Generator of Moving Objects*

• Up to 10000 users
• Velocities from 18 to 68 km/h

• Uniform and skewed query distributions

• Anonymity degree K in the range [10, 160]

Anonymity Strength (center-of-ASR)

ASR Size

Query Efficiency

Relocation Efficiency

Load Balancing

Conclusions

• LBS Privacy an important concern

• Existing solutions have no privacy guarantees
• Centralized approach has limitations
• Poor scalability, legal issues

• Contribution

• Anonymization with privacy guarantees
• hilbASR
• Extension to decentralized systems
• Improved scalability and availability
• No single point-of-attack/failure

Ongoing & Future Work

• Relational DB

• Employ space mapping techniques to achieve k-anonymity and l-diversity
• We outperform existing “state-of-the art”
• Space/Data Partitioning and Clustering

• Spatial anonymity

• Address anonymization of trajectories
• As opposed to point locations

Ongoing & Future Work

• Address anonymization of trajectories

• As opposed to point locations

• Infrastructure-less scenario

Bibliography on LBS Privacy

• http://anonym.comp.nus.edu.sg

Bibliography

• [Chow06] – Mokbel et al, A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services, ACM GIS ’06

• [Gru03] - Gruteser et al, Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking, MobiSys 2003

• [Ged05] – Gedik et al, Location Privacy in Mobile Systems: A Personalized Anonymization Model, ICDCS 2005

• [Mok06] – Mokbel et al, The New Casper: Query Processing for Location Services without Compromising Privacy, VLDB 2006

MobiHide

• Randomized ASR assembly technique:

• Also uses Hilbert ordering
• ASR chosen as random K-user sequence

• Advantages

• No global knowledge required
• Flat index structure (Chord DHT)

• Disadvantages

• No privacy guarantees for skewed query distributions
• but still strong anonymity in practice