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.