Differential privacy of identity query I am trying to understand some of the papers that present identity query mechanisms that satisfies differential privacy, for example the compressive mechanism which uses what they call a universal mechanism. What I mean by identity query is: given a dataset the mechanism which returns dataset back with some noise added to it. The problem that I have is how can we define the sensitivity of such a query mechanism, $Q(D)=D$? If we look at neighboring datasets, $D'$, which differs by one entry, the sensitivity is defined as:
$$
\max(|D-D'|_1) \text{ over all possible } D'
$$
But this is confusing because to me this is a nonsensical statement since $D$ and $D'$ are not in the same dimension ($D'$ has one less row than $D$) and we cannot compute the $L_1$ norm. Could you please explain to me what I am missing? 
 A: There are two ways to define "neighboring databases" in differential privacy. One version is the one you are thinking of: we start with $D$ which has $n$ data points in it (for example) and we look at $D' \subset D$ with $n - 1$ data points.
The other (and IMHO more common) version is to define $D$ and $D'$ as neighboring if they have the same number of elements and differ in a single element, so: $|D \cap D'| = n-1$ and $|D| = |D'| = n$. This is often written as $d_{H}(D,D') = 1$, where $d_H$ is the Hamming distance between the data sets: the idea being that if $D$ and $D'$ were both bit-vectors then "differing in a a single entry" corresponds to Hamming distance 1.
When publishing noisy data (the example you mention), the latter definition is more natural.
A: See this review paper, and the references therein.
https://arxiv.org/pdf/1602.01063.pdf
In short, implementing the identity query is equivalent to producing a synthetic data set. Some methods make synthetic data sets by first making a lower-dimensional summary of the data. In the example of the Compressive Mechanism, the summary is the size-k compressive measurements from the full sample of size n. That summary has a maximum it can change, when data sets differ by only one entry. The noise is applied in the summary-space, according to the summary's sensitivity, then decoded back out to a full-size synthetic data set.
A: Formally, what you're trying to do is to use the Laplace mechanism, which requires to compute the $\ell_1$-sensitivity of the function (query) $Q$ defined by $Q(D)=D$. If you look at how the $\ell_1$-sensitivity is defined (e.g. in Dwork and Roth's book), you will see that it is defined for numerical functions which take values in $\mathbb{R}^k$, where of course $k$ is fixed regardless of the input dataset. So, if you want to use the Laplace mechanism, you need to properly define $Q$ as a function which takes values in $\mathbb{R}^k$ for some $k$. Since $k$ is fixed, a simple identity mapping of an arbitrary set $D$ (seen e.g. as an $n \times m$ matrix) into $\mathbb{R}^{n \times m}$ will not work. You could instead define a proper encoding from the universe of datasets into $\mathbb{R}^k$, but doing so in a clever way which acts nicely with the $\ell_1$-sensitivity (and is easy to compute) is not trivial I believe.
Practically, to process a non-numerical query one typically uses the Exponential Mechanism instead. The Exponential Mechanism would allow you to use a query like $Q(D)=D$, but I believe this would not be a good choice from a utility standpoint because 'there are [too] many
databases in the range to dissipate the probability mass placed on this
“good” database' (see the book cited above, p. 70).
That said, there exist mechanisms, such as SmallDB, that achieve a much better privacy/utility tradeoff by producing a sort of smaller synthetic dataset that provably gives good utility for a certain family of queries (but not all of them, as you're trying to achieve with your mechanism).
