MS THESIS PRESENTATION: “Privacy Protection for Spatial Trajectories Against Brute-Force Attacks”
(Supervisor: Asst. Prof. Dr. Erman Ayday)
Computer Engineering Department
The prevalence of Global Positioning System (GPS) equipped mobile devices and wireless communication technologies have resulted in widespread development of location-based services (LBS). Typical examples of LBS include local search, routing, tracking, social networking, and context advertising. In terms of update frequency of location, LBS are divided into two categories: snapshot and continuous. Snapshot LBS request a user’s location only once to control features. Continuous LBS, on the other hand, require a user’s location in a dynamically periodic or on-demand manner. In the course of interaction with a continuous LBS application, the user reveals a sequence of location samples, namely, spatial trajectory, to service provider. Trajectory privacy in such services is of great importance, since adversaries may use the spatio-temporal sequential pattern to disclose the user’s personally identi_able information (PII) with high certainty. In order to prevent this from happening, service providers generally encrypt spatial trajectory data under the user’s password, and then store in their databases. However, potential adversaries may decrypt the encrypted database via a bruteforce attack. In other words, they try every possible value for a password until success is achieved. Although using high-entropy passwords have caused inconvenience for adversaries, the encryption schemes of service providers are vulnerable to this type of an attack due to the tendency of users to choose weak passwords. Also, if the rapid evaluation of computing technology and algorithmic advances are taken into consideration, even the use of a large password domain with conventional encryption can lead to the success of a brute-force attack that became feasible computationally. Thus it is crucial to assess privacy threats and take security countermeasures for spatial trajectories.
We present a system that incorporates honey encryption (HE) scheme that provides security beyond the brute-force bound in order to provide absolute protection for spatial trajectories against data breaches that involve computationally unbounded adversary. Our technique guarantees that decryption under any password will yield a plausible-looking trajectory. If an adversary decrypts an encrypted trajectory with a wrong password, it cannot eliminate that password, since the system returns an incorrect trajectory that is impossible to distinguish from the correct one. To e_ciently encode and decode a spatial trajectory, we build a precise tree-based distribution transforming encoder (DTE) as the fundamental requirement of HE. In addition, we introduce the methods to dynamically update the proposed DTE. To prove the security guarantee of our system, we evalute it considering several attacks with and without side information using a real-life GPS sampling data set taken from 537 taxis over 30 days.
DATE: 10 August 2018, Friday @ 10:30