Local Differential Privacy (LDP)

Unlike the Central Model where a trusted curator holds raw data, LDP operates under an untrusted aggregator assumption. The raw record never leaves the user's device. This eliminates the single point of failure—the central database—making it ideal for high-stakes data collection where the server cannot be trusted with plaintext.

The foundational primitive for LDP. To answer a sensitive binary question (e.g., 'Do you use drug X?'), the user flips a secret coin:

• Heads: Answer truthfully.
• Tails: Flip a second coin; answer 'Yes' for heads, 'No' for tails. This plausible deniability allows the aggregator to statistically reconstruct the true population proportion without ever knowing any specific individual's truth.

Modern LDP extends beyond binary questions to heavy hitter identification in categorical data. Protocols like RAPPOR (used by Google Chrome) encode a client's string into a Bloom filter, randomize the bits, and send the noisy report. The server aggregates millions of these reports to learn popular settings (e.g., hijacked homepages) without seeing any single user's actual configuration.

LDP injects significantly more noise than the central model to achieve the same epsilon (ε) guarantee, because noise is added by every user rather than once by a curator. To achieve high utility, LDP requires massive user bases (often millions) to average out the noise. The error typically scales by O(1/√n), demanding large n for accurate analytics.

For continuous data or gradient vectors in Federated Learning, LDP employs mechanisms like the Gaussian Mechanism or Laplace Mechanism applied per coordinate. A user clips their local gradient to bound L2 sensitivity, adds calibrated noise, and transmits the privatized vector. This prevents the server from performing gradient leakage attacks to reconstruct training data.

If a user reports multiple statistics over time, the privacy budget (ε) degrades additively. A system collecting daily telemetry must implement a privacy accountant on the device to track cumulative loss. Once the budget is exhausted, the device must stop reporting or reduce fidelity, enforcing a hard limit on data extraction from any single user.