Local Differential Privacy (LDP)

The fundamental architectural distinction of LDP. Unlike the central model, the server collecting data is assumed to be malicious or compromised. Privacy is guaranteed entirely by the client-side perturbation mechanism.

• Zero Raw Data Exposure: The aggregator never sees a true value.
• No Trusted Curator: Eliminates the need for a trusted third party to hold sensitive data.
• Strong User Agency: Individuals control their own privacy before data leaves their device.

The foundational algorithm for LDP, originating from survey methodology. For a binary attribute, a user flips a coin and answers truthfully only with a controlled probability.

• Plausible Deniability: A 'Yes' answer could be due to the coin flip, not the true value.
• Parameterization: Governed by the privacy budget ε; a smaller ε forces a higher probability of random answering.
• Aggregation: The true population proportion is estimated by correcting for the known noise injection rate.

Advanced LDP protocols designed to handle categorical data with many possible values, reducing the variance of basic randomized response.

• Unary Encoding (UE): Sends a length-d bit vector with 1 at the true position, then flips each bit with a specific probability.
• Optimized Local Hashing (OLH): Hashes the true value into a smaller domain before applying randomized response, optimizing the variance for large domains.
• Hadamard Response (HR): Uses a Hadamard matrix to encode the value, enabling efficient estimation with minimal communication cost.

The process of finding the most frequent items in a population under LDP, crucial for feature selection and dictionary learning.

• TreeHistogram Protocol: Users randomize a prefix of their value's bit representation, allowing the server to build a noisy prefix tree to identify frequent items without enumerating the full domain.
• Succinct Histograms: Memory-efficient structures that estimate frequencies of top-k items while suppressing the long tail of infrequent values.
• Application: Identifying popular emojis, URLs, or search queries without revealing any individual's specific input.

The inherent tension in LDP between data fidelity and protection. Because noise is added per-user, the total noise scales with the population, often requiring larger sample sizes than the central model.

• Error Scaling: Estimation error typically scales as O(1/√n), but with a constant factor that grows exponentially with the privacy parameter ε.
• Sample Size Requirement: Achieving useful accuracy for complex statistics demands a large user base to average out the injected noise.
• Local vs. Central: For the same ε, the central model generally offers higher utility, but LDP provides a stronger, user-verified trust model.

A hybrid architecture that bridges the utility gap between local and central models. Users still randomize data locally, but reports pass through a trusted shuffler that randomly permutes them before the analyzer sees them.

• Anonymity Effect: The shuffler breaks the link between a report and its source, amplifying the privacy guarantee from ε-local to ε-central.
• Prochlo Framework: A practical instantiation using secure enclaves for the shuffler, deployed in Google's metric collection.
• Benefit: Achieves near-central-model accuracy while maintaining the local model's protection against a compromised aggregator.

The fundamental architectural distinction. In the Central Model, a trusted curator collects raw data and applies a mechanism like the Laplace Mechanism before release. In the Local Model (LDP) , trust is eliminated; the individual perturbs data via mechanisms like Randomized Response before transmission. LDP provides stronger user-privacy but typically requires significantly more data to achieve the same utility as the central model due to the noise being applied per-record rather than globally.

A hybrid architecture bridging the utility gap between Central and Local DP. Users still randomize data locally, but reports are sent through a trusted shuffler that randomly permutes them before the analyzer sees them. This anonymity breaks the link between reports and users, amplifying the privacy guarantee through anonymity amplification. The shuffle model provides a better privacy-utility trade-off than pure LDP while maintaining a stronger trust model than a central curator.

LDP is implemented through specific perturbation algorithms:

• Randomized Response: For binary attributes, a user flips a coin and answers truthfully with probability p, otherwise answers randomly. Provides plausible deniability.
• Unary Encoding: A user encodes their value as a bit vector and flips each bit with a specific probability before sending.
• Local Hashing: The input domain is hashed into a smaller space, and only a single bit or value is perturbed and transmitted, reducing communication cost.

The privacy loss parameter ε quantifies the guarantee. A smaller ε (e.g., 0.1) means stronger privacy but more noise. In LDP, the budget is consumed locally per report. The Sequential Composition Theorem still applies: if a user reports k attributes, the total privacy loss is kε. This forces careful design of data collection protocols to avoid exhausting the budget on a single user's interaction.

The canonical LDP application. The goal is to discover the most frequent values (e.g., popular URLs, emojis) in a population without seeing any individual's raw input. Algorithms like RAPPOR (Google) and Apple's CMS use LDP to build histograms. The challenge is the heavy hitter discovery problem: efficiently finding frequent items in a massive domain (e.g., all possible strings) with limited communication and strong privacy.

An extension of LDP to location privacy. A user's exact location (x, y) is obfuscated by adding noise from a planar Laplace distribution before being sent to a location-based service. The guarantee ensures that locations within a radius r are indistinguishable, with the privacy level scaling linearly with distance. This allows for private proximity queries without revealing precise coordinates to an untrusted server.