A study on local differential privacy under adverse circumstances

Abstract

The rapid generation of information in the era of big data has made its analysis and the application of effective strategies increasingly essential across various fields, including business [97], healthcare [33], education [49], transportation [108], and public administration [66]. One method that has proven its immense potential for information gathering is crowdsourcing. However, the convenience of data collection through crowdsourcing also brings significant privacy concerns, particularly under adverse circumstances. Recent years have witnessed numerous data breach incidents, highlighting the vulnerability of personal information in centralized databases. Notable examples include the Yahoo breaches in 2013 and 2014 affecting 3 billion users [4], the Facebook-Cambridge Analytica scandal impacting over 50 million users [2], the Equifax leak compromising 143 million consumers' data [6], and the Marriott International hotels data breach affecting up to 500 million guests [3]. These incidents underscore the pressing need for robust privacy-preserving mechanisms, especially in adverse data collection environments. However, LDP faces significant challenges under adverse circumstances, particularly in three key areas: i) The curse of high dimensionality, which compromises aggregation accuracy. ii) Inefficient processing of sparse data with low-frequency values. iii) Vulnerability to Byzantine attacks that introduce poisoned data. This thesis presents a comprehensive study on enhancing LDP under adverse conditions, making the following contributions: i) We optimize privacy budget allocation among correlated attributes to improve utility in high-dimensional data scenarios. ii) For sparse data, we develop a novel approach using budget allocation and reinforcement learning to identify top-k values efficiently. iii) To combat Byzantine attacks, we establish robust LDP protocols that filter out poisoned data by analyzing varying user behaviors. Our research advances the field of secure and efficient data analytics under LDP by introducing innovative privacy-preserving mechanisms designed to perform effectively in challenging environments. This study not only addresses current limitations but also provides a foundation for future research in improving LDP's resilience and applicability under adverse circumstances.