Local differential privacy


Local differential privacy is a model of differential privacy with the added restriction that even if an adversary has access to the personal responses of an individual in the database, that adversary will still be unable to learn too much about the user's personal data. This is contrasted with global differential privacy, a model of differential privacy that incorporates a central aggregator with access to the raw data.

History

In 2003, Alexandre V. Evfimievski, Johannes Gehrke, Ramakrishnan Srikant gave a definition equivalent to local differential privacy. In 2008, Kasiviswanathan et al. gave a formal definition conforming with the standard definition of differential privacy.
The prototypical example of a locally differential private mechanism is the randomized response survey technique proposed by Stanley L. Warner in 1965, predating modern discussions of privacy. Warner's innovation was the introduction of the “untrusted curator” model, where the entity collecting the data may not be trustworthy. Before users' responses are sent to the curator, the answers are randomized in a controlled manner guaranteeing differential privacy while allowing valid population-wide statistical inferences.

ε-local differential privacy

Definition of ε-local differential privacy

Let ε be a positive real number and be a randomized algorithm that takes a user's private data as input. Let denote the image of. The algorithm is said to provide -local differential privacy if, for all pairs of user's possible private data and and all subsets of :


where the probability is taken over the randomness used by the algorithm.
The main difference between this definition and the standard definition of differential privacy is that in differential privacy the probabilities are of the outputs of an algorithm that takes all users' data and here it is on an algorithm that takes a single user's data.
Sometimes the definition takes an algorithm that has all users data as input, and outputs a collection of all responses.

Deployment

Local differential privacy has been deployed in several internet companies: