Methods of safely sharing general data
Differential privacy (DP) is a mathematically rigorous framework for releasing statistical information about datasets while protecting the privacy of individual data subjects. It enables a data holder to share aggregate patterns of the group while limiting information that is leaked about specific individuals. This is done by injecting carefully calibrated noise into statistical computations such that the utility of the statistic is preserved while provably limiting what can be inferred about any individual in the dataset. 
Another way to describe differential privacy is as a constraint on the algorithms used to publish aggregate information about a statistical database which limits the disclosure of private information of records in the database. For example, differentially private algorithms are used by some government agencies to publish demographic information or other statistical aggregates while ensuring confidentiality of survey responses, and by companies to collect information about user behavior while controlling what is visible even to internal analysts.
Roughly, an algorithm is differentially private if an observer seeing its output cannot tell whether a particular individual's information was used in the computation. Differential privacy is often discussed in the context of identifying individuals whose information may be in a database. Although it does not directly refer to identification and reidentification attacks, differentially private algorithms provably resist such attacks.
ε-differential privacy.
The 2006 Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith article introduced the concept of ε-differential privacy, a mathematical definition for the privacy loss associated with any data release drawn from a statistical database. (Here, the term "statistical database" means a set of data that are collected under the pledge of confidentiality for the purpose of producing statistics that, by their production, do not compromise the privacy of those individuals who provided the data.)
The definition of ε-differential privacy requires that a change to one entry in a database only creates a small change in the probability distribution of the outputs of measurements, as seen by the attacker. The intuition for the definition of ε-differential privacy is that a person's privacy cannot be compromised by a statistical release if their data are not in the database. In differential privacy, each individual is given roughly the same privacy that would result from having their data removed. That is, the statistical functions run on the database should not be substantially affected by the removal, addition, or change of any individual in the data.
How much any individual contributes to the result of a database query depends in part on how many people's data are involved in the query. If the database contains data from a single person, that person's data contributes 100%. If the database contains data from a hundred people, each person's data contributes just 1%. The key insight of differential privacy is that as the query is made on the data of fewer and fewer people, more noise needs to be added to the query result to produce the same amount of privacy. Hence the name of the 2006 paper, "Calibrating noise to sensitivity in private data analysis."
Definition.
Let ε be a positive real number and formula_1 be a randomized algorithm that takes a dataset as input (representing the actions of the trusted party holding the data). Let formula_2 denote the image of formula_1. 
The algorithm formula_1 is said to provide (ε, δ)-differential privacy if, for all datasets formula_5 and formula_6 that differ on a single element (i.e., the data of one person), and all subsets formula_7 of formula_2:
formula_9
where the probability is taken over the randomness used by the algorithm. This definition is sometimes called "approximate differential privacy", with "pure differential privacy" being a special case when formula_10. In the latter case, the algorithm is commonly said to satisfy ε-differential privacy (i.e., omitting formula_10).
Differential privacy offers strong and robust guarantees that facilitate modular design and analysis of differentially private mechanisms due to its composability, robustness to post-processing, and graceful degradation in the presence of correlated data.
Example.
According to this definition, differential privacy is a condition on the release mechanism (i.e., the trusted party releasing information "about" the dataset) and not on the dataset itself. Intuitively, this means that for any two datasets that are similar, a given differentially private algorithm will behave approximately the same on both datasets. The definition gives a strong guarantee that presence or absence of an individual will not affect the final output of the algorithm significantly.
For example, assume we have a database of medical records formula_5 where each record is a pair (Name, X), where formula_13 is a Boolean denoting whether a person has diabetes or not. For example:
Now suppose a malicious user (often termed an "adversary") wants to find whether Chandler has diabetes or not. Suppose he also knows in which row of the database Chandler resides. Now suppose the adversary is only allowed to use a particular form of query formula_14 that returns the partial sum of the first formula_15 rows of column formula_13 in the database. In order to find Chandler's diabetes status the adversary executes formula_17 and formula_18, then computes their difference. In this example, formula_19 and formula_20, so their difference is 1. This indicates that the "Has Diabetes" field in Chandler's row must be 1. This example highlights how individual information can be compromised even without explicitly querying for the information of a specific individual.
Continuing this example, if we construct formula_6 by replacing (Chandler, 1) with (Chandler, 0) then this malicious adversary will be able to distinguish formula_6 from formula_5 by computing formula_24 for each dataset. If the adversary were required to receive the values formula_14 via an formula_26-differentially private algorithm, for a sufficiently small formula_26, then he or she would be unable to distinguish between the two datasets.
Composability and robustness to post processing.
Composability refers to the fact that the joint distribution of the outputs of (possibly adaptively chosen) differentially private mechanisms satisfies differential privacy.
The other important property for modular use of differential privacy is robustness to post processing. This is defined to mean that for any deterministic or randomized function formula_38 defined over the image of the mechanism formula_1, if formula_1 satisfies ε-differential privacy, so does formula_41.
The property of composition permits modular construction and analysis of differentially private mechanisms and motivates the concept of the "privacy loss budget". If all elements that access sensitive data of a complex mechanisms are separately differentially private, so will be their combination, followed by arbitrary post-processing.
Group privacy.
In general, ε-differential privacy is designed to protect the privacy between neighboring databases which differ only in one row. This means that no adversary with arbitrary auxiliary information can know if one particular participant submitted their information. However this is also extendable. We may want to protect databases differing in formula_42 rows, which amounts to an adversary with arbitrary auxiliary information knowing if formula_42 particular participants submitted their information. This can be achieved because if formula_42 items change, the probability dilation is bounded by formula_45 instead of formula_46, i.e., for D1 and D2 differing on formula_42 items:formula_48Thus setting ε instead to formula_49 achieves the desired result (protection of formula_42 items). In other words, instead of having each item ε-differentially private protected, now every group of formula_42 items is ε-differentially private protected (and each item is formula_52-differentially private protected).
Hypothesis testing interpretation.
One can think of differential privacy as bounding the error rates in a hypothesis test. Consider two hypotheses:
Then, there are two error rates:
Ideal protection would imply that both error rates are equal, but for a fixed (ε, δ) setting, an attacker can achieve the following rates:
ε-differentially private mechanisms.
Since differential privacy is a probabilistic concept, any differentially private mechanism is necessarily randomized. Some of these, like the Laplace mechanism, described below, rely on adding controlled noise to the function that we want to compute. Others, like the exponential mechanism and posterior sampling sample from a problem-dependent family of distributions instead.
An important definition with respect to ε-differentially private mechanisms is sensitivity. Let formula_58 be a positive integer, formula_59 be a collection of datasets, and formula_60 be a function. One definition of the "sensitivity" of a function, denoted formula_61, can be defined by:formula_62where the maximum is over all pairs of datasets formula_5 and formula_6 in formula_59 differing in at most one element and formula_66 denotes the L1 norm. In the example of the medical database below, if we consider formula_67 to be the function formula_14, then the sensitivity of the function is one, since changing any one of the entries in the database causes the output of the function to change by either zero or one. This can be generalized to other metric spaces (measures of distance), and must be to make certain differentially private algorithms work, including adding noise from the Gaussian distribution (which requires the L2 norm) instead of the Laplace distribution.
There are techniques (which are described below) using which we can create a differentially private algorithm for functions, with parameters that vary depending on their sensitivity.
Laplace mechanism.
The Laplace mechanism adds Laplace noise (i.e. noise from the Laplace distribution, which can be expressed by probability density function formula_69, which has mean zero and standard deviation formula_70). Now in our case we define the output function of formula_71 as a real valued function (called as the transcript output by formula_71) as formula_73 where formula_74 and formula_75 is the original real valued query/function we planned to execute on the database. Now clearly formula_76 can be considered to be a continuous random variable, where
formula_77
which is at most formula_78. We can consider formula_79 to be the privacy factor formula_80. Thus formula_81 follows a differentially private mechanism (as can be seen from the definition above). If we try to use this concept in our diabetes example then it follows from the above derived fact that in order to have formula_71 as the formula_80-differential private algorithm we need to have formula_84. Though we have used Laplace noise here, other forms of noise, such as the Gaussian Noise, can be employed, but they may require a slight relaxation of the definition of differential privacy.
Randomized response.
A simple example, especially developed in the social sciences, is to ask a person to answer the question "Do you own the "attribute A"?", according to the following procedure:
(The seemingly redundant extra toss in the first case is needed in situations where just the "act" of tossing a coin may be observed by others, even if the actual result stays hidden.) The confidentiality then arises from the refutability of the individual responses.
But, overall, these data with many responses are significant, since positive responses are given to a quarter by people who do not have the "attribute A" and three-quarters by people who actually possess it. Thus, if "p" is the true proportion of people with "A", then we expect to obtain (1/4)(1-"p") + (3/4)"p" = (1/4) + "p"/2 positive responses. Hence it is possible to estimate "p".
In particular, if the "attribute A" is synonymous with illegal behavior, then answering "Yes" is not incriminating, insofar as the person has a probability of a "Yes" response, whatever it may be.
Although this example, inspired by randomized response, might be applicable to microdata (i.e., releasing datasets with each individual response), by definition differential privacy excludes microdata releases and is only applicable to queries (i.e., aggregating individual responses into one result) as this would violate the requirements, more specifically the plausible deniability that a subject participated or not.
Stable transformations.
A transformation formula_85 is formula_42-stable if the Hamming distance between formula_87 and formula_88 is at most formula_42-times the Hamming distance between formula_90 and formula_91 for any two databases formula_92. If there is a mechanism formula_93 that is formula_26-differentially private, then the composite mechanism formula_95 is formula_96-differentially private.
This could be generalized to group privacy, as the group size could be thought of as the Hamming distance formula_97 between
formula_90 and formula_91 (where formula_90 contains the group and formula_91 does not). In this case formula_95 is formula_103-differentially private.
Research.
Early research leading to differential privacy.
In 1977, Tore Dalenius formalized the mathematics of cell suppression. Tore Dalenius was a Swedish statistician who contributed to statistical privacy through his 1977 paper that revealed a key point about statistical databases, which was that databases should not reveal information about an individual that is not otherwise accessible. He also defined a typology for statistical disclosures.
In 1979, Dorothy Denning, Peter J. Denning and Mayer D. Schwartz formalized the concept of a Tracker, an adversary that could learn the confidential contents of a