Local Differential Privacy
Table of Contents
Local differential privacy (LDP) follows a decentralized paradigm that each client perturbs the local data before releasing, preserving populational information while protecting individual privacy. A common statistical tool frequency oracle is built on top of LDP that can handle various data frequency queries.
1. Local Differential Privacy
In centralized paradigm, we often assume a faithful third-party data center, however, this is not practical. LDP trades computational cost for better privacy.
1.1. Formal Definition
The difference is that, in LDP, each client runs a randomized protocol. The requirement is that the distribution of the messages sent by each user individually should already satisfy the DP guarantee.
Suppose each client runs a randomized policy locally \(R(x)\) on their local input. The protocol satisfies \(\epsilon\)-LDP if
\begin{equation} \frac{\mathbb{P}[R(x) = T]}{\mathbb{P}[R(x') = T]} \le \exp(\epsilon) \end{equation}for every pair of input \(x,x'\). The formula tells that after seeing one user’s message, the server cannot confidently determine which input produces it. This privacy guarantee is imposed on client-side data, not the whole dataset.
The key insight is that, although the privacy is preserved at individual level, at populational level, the desired information is still preserved. Because the noise might average out.