Local Differential Privacy

Local differential privacy (LDP) is a privacy model where noise is added to each individual's data before it leaves their device, ensuring that the data collector never sees raw personal information. Unlike central differential privacy where a trusted server collects raw data and adds noise during computation, LDP requires no trusted central party.

How LDP Works

• On-Device Perturbation: Each user's device applies a randomized mechanism to their true data before sending it to the server.
• Plausible Deniability: Any individual response could have been generated from multiple true values — the user can always deny their actual data.
• Aggregate Recovery: While individual responses are noisy and unreliable, the server can statistically recover accurate aggregate statistics from many responses through debiasing techniques.

Classic LDP Mechanisms

• Randomized Response: For a binary question, the user answers truthfully with probability p and lies with probability 1-p. The server can compute the true proportion by correcting for the known lie rate.
• RAPPOR (Google): Users encode their data as a bit vector, randomly flip each bit, and send the noisy vector. Allows collection of frequency data with strong privacy.
• Unary Encoding: Encode categorical data as a one-hot vector and perturb each bit independently.

Real-World Deployments

• Apple: Collects emoji usage, typing patterns, and Safari suggestions in iOS using LDP.
• Google Chrome: Collects browsing statistics and homepage settings using RAPPOR.
• Microsoft: Uses LDP in Windows telemetry collection.

Advantages

• No Trust Required: Users don't need to trust the data collector — privacy is guaranteed by the on-device noise.
• Regulatory Compliance: Strong alignment with GDPR's data minimization principle.

Disadvantages

• Utility Loss: LDP requires significantly more noise than central DP to achieve the same privacy level, degrading data utility.
• Large Sample Size: Accurate aggregate statistics require many participants to overcome individual noise.

LDP is the gold standard for privacy when data collectors cannot be trusted, though it comes at a significant accuracy cost compared to central DP.