Local Differential Privacy (LDP)

The defining characteristic of LDP is that the privacy mechanism executes on the client device. Users perturb their own data using a randomized algorithm—typically adding noise drawn from a Laplace or Gaussian distribution—before the data leaves their control. This guarantees that raw, unmodified records are never transmitted or stored centrally.

• Client-side execution: The noise injection happens in the browser, mobile app, or edge device.
• Plausible deniability: The server receives a value that is statistically correlated with the true value but never definitively identifies it.
• Common mechanisms: Randomized Response for binary attributes, the Laplace mechanism for numeric queries, and the Generalized Randomized Response for categorical data.

LDP operates under the untrusted aggregator assumption. Unlike Central Differential Privacy, where a trusted curator collects raw data and adds noise during analysis, LDP assumes the data collector is potentially adversarial or could be compromised. Privacy is guaranteed against the server, other users, and external observers.

• No trusted third party: Eliminates the need for a data curator with access to raw records.
• Resilience to server breaches: A database breach reveals only randomized values, not ground truth.
• User-to-user privacy: One user's guarantee holds even if all other users collude with the server.

LDP introduces significantly more noise than the central model to achieve the same epsilon guarantee. Because each user randomizes independently, the variance accumulates across the population. Accurate statistical estimates require a large user base to average out the injected noise.

• Sample size dependency: Utility scales with the square root of the number of users; small cohorts yield noisy, unreliable aggregates.
• Frequency estimation: Estimating the popularity of a category requires debiasing the randomized responses using knowledge of the perturbation probability.
• Heavy hitters: Identifying the most frequent items under LDP demands specialized protocols like Apple's Sequence Fragment Puzzle or Google's RAPPOR to manage the large domain of possible strings.

Major technology platforms have deployed LDP at scale to collect telemetry and usage statistics without accessing individual user behavior. These implementations demonstrate practical viability but also reveal the challenges of high-dimensional data.

• Apple's implementation: Uses LDP to collect emoji usage, QuickType suggestions, and Safari health data. Employs the Sequence Fragment Puzzle technique to handle large domains of potential strings.
• Google's RAPPOR: The Randomized Aggregatable Privacy-Preserving Ordinal Response system collects Chrome browser statistics, encoding values into Bloom filters before applying randomized response.
• Microsoft's Telemetry: Applies LDP for collecting Windows application usage statistics, using a privatization mechanism tailored to heavy hitter identification.

Applying LDP to complex queries beyond simple counts requires specialized protocols. These algorithms decompose high-dimensional data or complex statistics into primitives that can be privatized locally.

• Frequency Oracles: Protocols like Optimal Unary Encoding (OUE) and Symmetric Unary Encoding (SUE) optimize the variance of frequency estimates for categorical data.
• Mean Estimation: The Stochastic Rounding technique and Duchi's mechanism provide LDP for real-valued attributes by discretizing and randomizing numeric values.
• Key-Value Data: The PrivKV protocol extends LDP to key-value pairs, allowing private collection of sparse, high-dimensional data like browser settings where most keys are absent.

When applied to federated learning, LDP ensures that individual model gradients are privatized before aggregation. Each client clips and perturbs their local gradient update, guaranteeing that the central server cannot invert the gradient to reconstruct private training data.

• Gradient sanitization: Clients clip the L2 norm of their per-sample gradients and add Gaussian noise, implementing a local version of DP-SGD.
• Secure aggregation synergy: LDP can be combined with secure aggregation protocols to provide defense-in-depth, protecting against both the server and inference attacks on the aggregated model.
• Communication overhead: The noise added for LDP can dominate the signal in high-dimensional gradient vectors, requiring careful privacy budget allocation across training rounds.