The universal popularity of GPS-enabled mobile devices and traffic navigation services has fueled the growth of trajectory data, as evidenced by Uber Movement and NYC taxi data release. Although trajectory data can generate valuable insights and value-added services for many, publishing this data while respecting mobile users' privacy has been a long-standing challenge. In this paper we present DP-Star, a methodical framework for publishing trajectory data with differential privacy guarantee as well as high utility preservation. DP-Star relies on a novel combination of several components. First, DP-Star's normalization algorithm uses the MDL metric to summarize raw trajectories using their representative points, thereby achieving a desirable trade-off between the preciseness and conciseness of their information content. Second, DP-Star constructs a density-aware grid which ensures spatial densities can be preserved despite the noise added to satisfy differential privacy. Third, DP-Star preserves the correlations between trajectories' end points through a private trip distribution, and intermediate points through a private Markov mobility model. Finally, DP-Star estimates users' trip lengths using a median length estimation method, and generates synthetic trajectories that preserve both differential privacy and high utility. Our experimental comparison shows that DP-Star significantly outperforms existing approaches in terms of trajectory utility and accuracy.

Local Differential Privacy (LDP) is popularly used in practice for privacy-preserving data collection. Although existing LDP protocols offer high utility for large user populations (100,000 or more users), they perform poorly in scenarios with small user populations (such as those in the cybersecurity domain) and lack perturbation mechanisms that are effective for both ordinal and non-ordinal item sequences while protecting sequence length and content simultaneously. In this paper, we address the small user population problem by introducing the concept of Condensed Local Differential Privacy (CLDP) as a specialization of LDP, and develop a suite of CLDP protocols that offer desirable statistical utility while preserving privacy. Our protocols support different types of client data, ranging from ordinal data types in finite metric spaces (numeric malware infection statistics), to non-ordinal items (OS versions, transaction categories), and to sequences of ordinal and non-ordinal items. Extensive experiments are conducted on multiple datasets, including datasets that are an order of magnitude smaller than those used in existing approaches, which show that proposed CLDP protocols yield high utility. Furthermore, case studies with Symantec datasets demonstrate that our protocols accurately support key cybersecurity-focused tasks of detecting ransomware outbreaks, identifying targeted and vulnerable OSs, and inspecting suspicious activities on infected machines.

Local Differential Privacy (LDP) is a popular standard for privacy-preserving data collection. Numerous LDP protocols have been proposed in the literature which differ in how they provide higher utility in different settings. Yet, few have engaged in analyzing the privacy relationships of these protocols under varying settings, and consequently, it is non-trivial to select which LDP protocol is best to use in a newly emerging application. In this paper, we present an adversarial approach to protocol analysis and selection and make three original contributions. First, we introduce a Bayesian adversary to analyze the privacy relationships of LDP protocols under varying settings. We show that different protocols have substantially different responses to the attack effectiveness of the Bayesian adversary, measured in terms of Adversarial Success Rate (ASR). Second, we provide a formal and empirical analysis on a set of privacy and utility-critical factors, including encoding parameters, privacy budget, data domain, adversarial knowledge, and statistical distribution. We show that different settings of these factors have significant effects on the ASRs of LDP protocols, and no protocol provides consistently low ASR across all settings. Third, we design and develop LDPLens, a prototype implementation of our proposed framework. Given a data collection scenario with various factors and constraints, LDPLens enables optimized selection of a desirable LDP protocol for the given scenario. We evaluate the effectiveness of LDPLens using three case studies with real-world datasets. Results show that LDPLens recommends a different protocol in each case study, and the protocol recommended by LDPLens can yield up to 1.5–2 fold reduction in utility loss, ASR or privacy budget compared to a randomly selected protocol.

With the continued explosion of digitized data, data mining and data collection have become more prevalent. With this growth, we have also seen increased concern over data privacy and intellectual property. Within this environment, an important question has emerged: Can machine learning and data mining techniques be leveraged without compromising privacy? This paper revisits the concepts and techniques of privacy-preserving decision tree learning, a fundamental model of inductive learning. We first examine different privacy risks during decision tree based inductive learning processes, including the sensitivity of private input data and potential privacy risks induced by inference over both the learning output and the intermediate results of inductive learning iterations. We then review and compare the privacy notions and properties of three orthogonal and yet complimentary technical frameworks: randomization-based data obfuscation, differential privacy, and secure multiparty computation. We analyze their effectiveness and review representative approaches in each of these three frameworks. Finally, we highlight some of the open challenges to privacy-preserving solutions for decision tree learning.