Collecting and Analyzing Data Jointly from Multiple Services under Local Differential Privacy

Users' sensitive data can be collected and analyzed under local differential privacy (LDP) without the need to trust the data collector. Most previous work on LDP can be applied when each user's data is generated and collected from a single service or data source. In a more general and practical setting, sensitive data of each user needs to be collected under LDP from multiple services independently and can be joined on, e.g., user id. In this paper, we address two challenges in this setting: first, how to prevent the privacy guarantee from being weakened during the joint data collection; second, how to analyze perturbed data jointly from different services. We introduce the notation of user-level LDP to formalize and protect the privacy of a user when her joined data tuples are released. We propose mechanisms and estimation methods to process multidimensional analytical queries, each with sensitive attributes (in its aggregation and predicates) collected and perturbed independently in multiple services. We also introduce an online utility optimization technique for multi-dimensional range predicates, based on consistency in domain hierarchy. We conduct extensive evaluations to verify our theoretical results using synthetic and real datasets.