LDP-IDS: Local Differential Privacy for Infinite Data Streams

Abstract

Streaming data collection is essential to real-time data analytics in various IoTs and mobile device-based systems, which, however, may expose end users' privacy. Local differential privacy (LDP) is a promising solution to privacy-preserving data collection and analysis. However, existing few LDP studies over streams are either applicable to finite streams only or suffering from insufficient protection. This paper investigates this problem by proposing LDP-IDS, a novel $w$-event LDP paradigm to provide practical privacy guarantee for infinite streams at users end, and adapting the popular budget division framework in centralized differential privacy (CDP). By constructing a unified error analysi for LDP, we first develop two adatpive budget division-based LDP methods for LDP-IDS that can enhance data utility via leveraging the non-deterministic sparsity in streams. Beyond that, we further propose a novel population division framework that can not only avoid the high sensitivity of LDP noise to budget division but also require significantly less communication. Based on the framework, we also present two adaptive population division methods for LDP-IDS with theoretical analysis. We conduct extensive experiments on synthetic and real-world datasets to evaluate the effectiveness and efficiency pf our proposed frameworks and methods. Experimental results demonstrate that, despite the effectiveness of the adaptive budget division methods, the proposed population division framework and methods can further achieve much higher effectiveness and efficiency.

arXiv commentaccepted to SIGMOD'22

References in corpus (12)

• RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
• LoPub: High-Dimensional Crowdsourced Data Publication with Local Differential Privacy
• Collecting Telemetry Data Privately
• Extremal Mechanisms for Local Differential Privacy
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy
• Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
• Private Decayed Sum Estimation under Continual Observation
• Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]
• Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy
• Local Differential Privacy for Evolving Data
• DPCrowd: Privacy-preserving and Communication-efficient Decentralized Statistical Estimation for Real-time Crowd-sourced Data

Cited by in corpus (5)

• Practical Differentially Private and Byzantine-resilient Federated Learning
• Benchmarking Secure Sampling Protocols for Differential Privacy
• No One Size (PPM) Fits All: Towards Privacy in Stream Processing Systems
• Fine-grained Manipulation Attacks to Local Differential Privacy Protocols for Data Streams
• Defense against Poisoning Attacks under Shuffle-DP