trajectory split swap   privacy
226567815
PAPU: Pseudonym Swap With Provable Unlinkability Based on Differential Privacy in VANETs
Nowadays, the pseudonym swap has become the mainstream technology for protecting vehicles' trajectory privacy in vehicle ad hoc networks. However, the existing pseudonym swap methods cannot strictly provide the unlinkability between the new pseudonym and old pseudonym of the vehicle due to the lack of theoretical privacy guarantee, resulting in severe leakages of vehicles' trajectory privacy. Our experiment also proves this point and we find that existing works may cause vehicle's pseudonyms to be linked with a probability higher than 60% because they always choose two vehicles with very different driving states (e.g. speeds, directions, and positions) to swap their pseudonyms. To solve this issue, we first give a formal privacy definition based on generalized differential privacy, called pseudonym indistinguishability, to provide a strict unlinkability for pseudonym swap. Then, we design an appropriate utility metric and a new pseudonym swap mechanism, which selects a pseudonym for a vehicle by adapting a differential privacy exponential mechanism to satisfy pseudonym indistinguishability. Abstracting from attackers' prior knowledge, we can strictly guarantee that if two vehicles have a high similarity of driving states, it is impossible for attackers to link the vehicles and their pseudonyms after the swap. Theoretical analyses prove that our mechanism satisfies the proposed privacy definition, thus ensuring the unlinkability between the new pseudonym and the old pseudonym. Extensive experiments on a real data set show that our work only requires about 50% of pseudonym quantities compared to other works and can make the vehicle successfully complete the swap process with a probability of more than 90% which is higher than any of existing works.
IEEE Internet of Things Journal
Xinghua Li Huijuan Zhang Yanbing Ren Siqi Ma Bin Luo Jian Weng Jian-Feng Ma Xiaoming Huang
210040454
Storage Efficient Trajectory Clustering and k NN for Robust Privacy Preserving Spatio Temporal Databases
The need to store massive volumes of spatio temporal data has become a difficult task as GPS capabilities and wireless communication technologies have become prevalent to modern mobile devices. As a result, massive trajectory data are produced, incurring expensive costs for storage, transmission, as well as query processing. A number of algorithms for compressing trajectory data have been proposed in order to overcome these difficulties. These algorithms try to reduce the size of trajectory data, while preserving the quality of the information. In the context of this research work, we focus on both the privacy preservation and storage problem of spatio temporal databases. To alleviate this issue, we propose an efficient framework for trajectories representation, entitled DUST (DUal based Spatio temporal Trajectory) by which a raw trajectory is split into a number of linear sub trajectories which are subjected to dual transformation that formulates the representatives of each linear component of initial trajectory; thus, the compressed trajectory achieves compression ratio equal to M 1 To our knowledge, we are the first to study and address k NN queries on nonlinear moving object trajectories that are represented in dual dimensional space. Additionally, the proposed approach is expected to reinforce the privacy protection of such data. Specifically, even in case that an intruder has access to the dual points of trajectory data and try to reproduce the native points that fit a specific component of the initial trajectory, the identity of the mobile object will remain secure with high probability. In this way, the privacy of the k anonymity method is reinforced. Through experiments on real spatial datasets, we evaluate the robustness of the new approach and compare it with the one studied in our previous work.
Algorithms
Elias Dritsas Andreas Kanavos Maria Trigka Spyros Sioutas Athanasios K Tsakalidis
2854330
Trajectory anonymisation based on graph split using EMD
Analysing and mining trajectories pose new challenges for trajectory privacy. We are addressing privacy issue for offline (historical) trajectories which are generally published for research. A fundamental research question in trajectory privacy domain is of trajectory anonymisation. k anonymity is used as a standard for privacy which ensures that every entity in the dataset is indistinguishable from (k 1) other entities. The proposed work aims at anonymising trajectories based on graph split method. We have used technique of constructing trajectory graph to simulate spatial and temporal relations of trajectories, based on which trajectory k anonymity sets are found through graph split. For the purpose, we have proposed a novel method that uses earth mover's distance as a metric to find trajectory k anonymity sets in contrast to Euclidean distance. It is discovered through a series of experiments that the proposed method is outperforming in terms of low information loss and computation time.
Int. J. Comput. Sci. Eng.
Priti Jagwani Saroj Kaushik
3234328
Privacy Preserving Trajectory Publication against Parking Point Attacks
GPS data is becoming more and more popular due to massive usage of global positioning systems, other location based devices and services. However, publishing original GPS data to the public or a third party for data mining and analysis could cause serious privacy issues. In this paper, we perform a study on taxi GPS data and identify a new type of attack called a parking points attack. In a parking points attack, an adversary utilizes parking habits of taxi drivers to re identify related victims in a published taxi trajectory dataset. To against such attacks, we introduce the concept of spatial temporal tunnel to swap sub trajectories of taxis. Using real GPS trajectories from more than 12,000 taxis, we demonstrate that the proposed approach effectively limits parking point attacks. As a result, more than 55% of trajectories can be re identified at a probability of 1 in original trajectory dataset, but only 8.6% of trajectories can be re identified in our swapped trajectory dataset.
2013 IEEE 10th International Conference on Ubiquitous Intelligence and Computing and 2013 IEEE 10th International Conference on Autonomic and Trusted Computing
Peipei Sui Tianyu Wo Zhangle Wen Xianxian Li
198329161
Intelligent route planning on large road networks with efficiency and privacy
Abstract When using Location Based Services (LBS) intelligent route planning becomes crucial to improve service quality and user experience. The state of the art G tree structure enables efficient route planning on large road networks, but lacks usability and intelligence. In this paper, we first propose a comprehensive service framework, called BCloud IFog, which consists of blind cloud servers and intelligent fog servers. Then, we propose an Outsourced Real time Route Planning (OR2P) scheme, where the search index is built as a G* tree structure and each G* tree leaf node is split into a set of non confidential outsourced graphs. Compared with the G tree structure, our work has the following advantages: (1) Higher usability. Unlike the G tree structure requiring the user to perform all calculations in the search process, it delegates the most of computations to cloud servers. (2) Privacy Protection. Unlike the straightforward solution that directly outsource the G tree structure, it outsources only the non confidential graphs such that cloud servers cannot infer the original road network or user trajectory. (3) Better intelligence. Unlike the G tree structure handles only static route planning, it allows fog servers to make route plans based on the dynamic real time traffic status. Extensive experiments on real data sets demonstrate the effectiveness of our work.
J. Parallel Distributed Comput.
Qin Liu Panlin Hou Guojun Wang Tao Peng Shaobo Zhang
18434170
Distributed mapping with privacy and communication constraints: Lightweight algorithms and object based models
We consider the following problem: a team of robots is deployed in an unknown environment and it has to collaboratively build a map of the area without a reliable infrastructure for communication. The backbone for modern mapping techniques is pose graph optimization, which estimates the trajectory of the robots, from which the map can be easily built. The first contribution of this paper is a set of distributed algorithms for pose graph optimization: rather than sending all sensor data to a remote sensor fusion server, the robots exchange very partial and noisy information to reach an agreement on the pose graph configuration. Our approach can be considered as a distributed implementation of a two stage approach that already exists, where we use the Successive Over Relaxation and the Jacobi Over Relaxation as workhorses to split the computation among the robots. We also provide conditions under which the proposed distributed protocols converge to the solution of the centralized two stage approach. As a second contribution, we extend the proposed distributed algorithms to work with the object based map models. The use of object based models avoids the exchange of raw sensor measurements (e.g. point clouds or RGB D data) further reducing the communication burden. Our third contribution is an extensive experimental evaluation of the proposed techniques, including tests in realistic Gazebo simulations and field experiments in a military test facility. Abundant experimental evidence suggests that one of the proposed algorithms (the Distributed Gauss Seidel method) has excellent performance. The Distributed Gauss Seidel method requires minimal information exchange, has an anytime flavor, scales well to large teams (we demonstrate mapping with a team of 50 robots) is robust to noise, and is easy to implement. Our field tests show that the combined use of our distributed algorithms and object based models reduces the communication requirements by several orders of magnitude and enables distributed mapping with large teams of robots in real world problems. The source code is available for download at https:/cognitiverobotics.github.io/distributed mapper/
Int. J. Robotics Res.
Siddharth Choudhary Luca Carlone Carlos Nieto-Granda John G Rogers Henrik I Christensen Frank Dellaert
216651392
Privacy Preserving Publication of Mobility Data with High Utility
An increasing amount of mobility data is being collected every day by different means, e.g. By mobile phone operators. This data is sometimes published after the application of simple anonymization techniques, which might lead to severe privacy threats. We propose in this paper a new solution whose novelty is two fold. Firstly, we introduce an algorithm designed to hide places where a user stops during her journey (namely points of interest) by enforcing a constant speed along her trajectory. Secondly, we leverage places where users meet to take a chance to swap their trajectories and therefore confuse an attacker.
2015 IEEE 35th International Conference on Distributed Computing Systems
Vincent Primault Sonia Ben Mokhtar Lionel Brunie
1404980
Privacy: preserving trajectory collection
In order to provide context aware Location Based Services, real location data of mobile users must be collected and analyzed by spatio temporal data mining methods. However, the data mining methods need precise location data, while the mobile users want to protect their location privacy. To remedy this situation, this paper first formally defines novel location privacy requirements. Then, it briefly presents a system for privacy preserving trajectory collection that meets these requirements. The system is composed of an untrusted server and clients communicating in a P2P network. Location data is anonymized in the system using data cloaking and data swapping techniques. Finally, the paper empirically demonstrates that the proposed system is effective and feasible.
GIS '08
Gyozo Gidofalvi Xuegang Huang T Pedersen
5008325
Deep Arm/Ear ECG Image Learning for Highly Wearable Biometric Human Identification
In this study, to advance smart health applications which have increasing security/privacy requirements, we propose a novel highly wearable ECG based user identification system, empowered by both non standard convenient ECG lead configurations and deep learning techniques. Specifically, to achieve a super wearability, we suggest situating all the ECG electrodes on the left upper arm, or behind the ears, and successfully obtain weak but distinguishable ECG waveforms. Afterwards, to identify individuals from weak ECG, we further present a two stage framework, including ECG imaging and deep feature learning/identification. In the former stage, the ECG heartbeats are projected to a 2D state space, to reveal heartbeats' trajectory behaviors and produce 2D images by a split then hit method. In the second stage, a convolutional neural network is introduced to automatically learn the intricate patterns directly from the ECG image representations without heavy feature engineering, and then perform user identification. Experimental results on two acquired datasets using our wearable prototype, show a promising identification rate of 98.4% (single arm ECG) and 91.1% (ear ECG) respectively. To the best of our knowledge, it is the first study on the feasibility of using single arm ECG/ear ECG for user identification purpose, which is expected to contribute to pervasive ECG based user identification in smart health applications.
Annals of Biomedical Engineering
Qingxue Zhang Dian Zhou
212862528
Swapping trajectories with a sufficient sanitizer
Abstract Real time mobility data is useful for several applications such as planning transports in metropolitan areas or localizing services in towns. However, if such data is collected without any privacy protection it may reveal sensible locations and pose safety risks to an individual associated to it. Thus, mobility data must be anonymized preferably at the time of collection. In this paper, we consider the SwapMob algorithm that mitigates privacy risks by swapping partial trajectories. We formalize the concept of sufficient sanitizer and show that the SwapMob algorithm is a sufficient sanitizer for various statistical decision problems. That is, it preserves the aggregate information of the spatial database in the form of sufficient statistics and also provides privacy to the individuals. This may be used for personalized assistants taking advantage of users' locations, so they can ensure user privacy while providing accurate response to the user requirements. We measure the privacy provided by SwapMob as the Adversary Information Gain, which measures the capability of an adversary to leverage his knowledge of exact data points to infer a larger segment of the sanitized trajectory. We test the utility of the data obtained after applying SwapMob sanitization in terms of Origin Destination matrices, a fundamental tool in transportation modelling.
Pattern Recognit. Lett.
Julian Salas David Megias Vicenc Torra Marina Toger J Dahne Raazesh Sainudiin