Privacy Preservation in Location Based Services

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


FYT Presentation & Demonstration

Title: "Privacy Preservation in Location Based Services"

By

Mr. Kevin Keliang ZHAO

Abstract

Privacy in location based services consists of identity privacy and
location privacy. Identity privacy requires that the identity of the
issuer of a spatial query cannot be pinpointed. Location privacy
ensures that exact location of each user is not disclosed. In this
thesis we concentrate on Spatial K-anonymity (SKA) which exploits the
concept of K-anonymity in order to protect the identity of users from
location-based attacks. The main idea of SKA is to replace the exact
location of a user U with an anonymizing spatial region (ASR) that
contains at least K-1 other users, so that an attacker can pinpoint U
with probability at most 1/K. However, simply generating an ASR that
includes K users is not sufficient for SKA. Motivated by this fact, we
first define reciprocity, a property that guarantees spatial
anonymity. Then, we propose a framework for generating reciprocal
algorithms using a spatial index on the user locations. We present
several variants of Rtree Cloak, a novel SKA algorithm based on
R-trees, which provide different trade-offs on effectiveness (i.e.,
ASR size) and efficiency. We verify the applicability of the proposed
techniques to large problem settings through extensive experiments. We
also discuss how Rtree Cloak can be modified according to the
knowledge available to the attacker.


Date:			Wednesday, 6 Jun 2007

Time:			3pm to 4pm

Venue:			Room 3301A
  			Lifts 17-18

Advisor:		Dr. Dimitris Papadias

2nd Reader:		Dr. Lei Chen


**** ALL are Welcome ****