Locally differentially private mechanisms for sequential and high-dimensional data analysis

With the increasing need for data privacy and protection, local differential privacy (LDP) has emerged as a widely accepted standard for privacy-preserving data col- lection. While LDP has been studied extensively for singular data, its application to sequential and multidimensional data remains underexplored. In this thesis, we propose novel LDP mechanisms for advancing the state-of-the-art in the application of LDP to these two data types. First, we propose Prima for learning discrete-time Markov chain models from sequential data under LDP. Markov chains are frequently used in the analysis and modeling of sequential data such as location traces, time series, natural language, and speech. However, considering that many such data sources are privacy-sensitive, it is imperative to design privacy-preserving methods for learning Markov chains. Prima addresses this need. In Prima, each user locally encodes and perturbs their sequential record on their own device using LDP protocols. For this purpose, we adapt two bitvector-based LDP protocols (RAPPOR and OUE); and furthermore, we develop a novel extension of the GRR protocol called AdaGRR. We also propose to utilize custom privacy budget allocation strategies for perturbation, which enable uneven splitting of the privacy budget to better preserve utility in cases with uneven sequence lengths. On the server side, Prima uses novel algorithms for estimating Markov probabilities from perturbed data. We experimentally evaluate Prima using three real-world datasets, four utility metrics, and various combinations of privacy budget and budget allocation strategies. Results show that Prima enables learning Markov chains with high utility and low error compared to Markov chains learned without privacy constraints. Second, we propose MCM (Matrix-Based Data Collection Mechanism), a novel LDP mechanism for the collection of multidimensional data. In MCM, each user encodes their multidimensional record into a bitmatrix. The rows of the bitmatrix are perturbed in a way that satisfies LDP. Then, the key contribution of MCM lies in its novel server-side estimation process, which enables the server to recover co- occurrence counts of all pairs of values in attribute domains. We utilize MCM to perform feature selection from multidimensional data using two popular feature se- lection metrics: information gain and chi-square. We experimentally evaluate MCM and the accompanying feature selection algorithms using three datasets, two utility metrics, and varying privacy budgets. Furthermore, we compare our solution with LDP-FS, a state-of-the-art solution for feature selection under LDP. We experimen- tally show that our solution yields more accurate information gain and chi-square values compared to LDP-FS, thereby improving the state-of-the-art. Furthermore, we demonstrate that correlations between attributes are accurately preserved in feature selection while LDP is satisfied.