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?

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.

• Is there any ordering of the strength between the two adjacency definitions? I.e. can we claim that DP mechanisms satisfying second adjacency definition will inherit DP property according to the first adjacency definition?
– Dion
Commented Jan 21, 2020 at 15:24
• well, actually replacing an element in a dataset can be written as a composition of one addition and one removal of a datapoint - hence it seems to hold in general that if algorithm is $(\varepsilon, \delta)$-DP under second adjacency definition (Hamming distance equals 1), it will also be $(\frac{1}{2}\varepsilon, \frac{1}{2}\delta)$ under first adjacency definition.
– Dion
Commented Jan 21, 2020 at 19:06
• This answer has two problems: (1) It does not address the core of the question, which is about using the Laplace mechanism for the identity query. Even if you use bounded DP (the second one), the Laplace mechanism still needs to be defined properly. Using bounded DP the Laplace mechanism could be used, but it's easy to check that it would completely destroy utility. DP cannot really release "noisy" versions of a dataset by adding noise directly to records. Commented May 16, 2022 at 12:15
• (2) Bounded DP is a weak definition of DP which essentially reveals the size of the dataset, and should not be used. Unbounded DP should be used instead, and hence neighboring datasets always differ in size. Commented May 16, 2022 at 12:20

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.

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).