Lowering the cost of anonymization

3.1.3 Passive vs. active attackers

In this section and the rest of this chapter, we assume that the criterion introduced in Definition 54 is satisfied: the data-generating distributions considered are always acceptable. For simplicity, we also assume that the sensitive property is the value of one record. Under these conditions, any value of the partial knowledge $ˆ B$ is compatible with any value of the sensitive record $D (i) = t$ , since these two events are independent. This also allows us to only consider the formalism of NPr; since it is equivalent with CausDP under this criterion (Proposition 24).

Correlations in the data are not the only issue to account for when limiting the attacker’s background knowledge in DP. Another important question is whether the attacker simply receives some partial knowledge passively, or whether the attacker can actively influence the data. In this section, we show how to model these two situations by adapting the notion of a privacy loss random variable to model an attacker with partial knowledge, and we explore the relationship between the two corresponding definitions. To help understand this distinction, in this section, we consider the following example.

Example 7 (Thresholding). 1000 people take part in a Yes/No-referendum. Each person votes “Yes” with some probability, independently from the others. The mechanism $M$ counts the number of “Yes” votes, but only returns this if it is above 100; otherwise it returns $⊥$ . The partial knowledge $B$ contains the votes of 100 participants, and the attacker wants to know the vote of another individual $D (i)$ . We will see that in case the probability that each person votes “Yes” is very small (say, $1 0^{- 7}$ ), the privacy of this scheme will depend on whether the attacker is passive or active.

Privacy loss random variable for partial knowledge

In Section 2.2.2, we introduced the privacy loss random variable (Definition 13), defined as:

L_{D_{1} ∕ D_{2}}^{M} (O) = ln \frac{P [M (D_{1}) = O]}{P [M (D_{2}) = O]} .

The PLRV quantifies how much information is revealed by the output of a mechanism, and we saw in Proposition 8 that a mechanism $M$ is $(ε, δ)$ -DP iff for all neighboring databases $D_{1}$ and $D_{2}$ , and all outputs $O$ :

E O \sim M (D_{1}) [max (0, 1 - e_{D_{1} / D_{2}}^{ε - L_{D_{1} / D_{2}} (O)})] \leq δ .

Now, suppose the attacker only has partial knowledge about the data. How to adapt the definition of the PLRV to this setting? The data comes from a distribution $θ$ , and the attacker tries to distinguish between $D (i) = t$ and $D (i) = t^{'}$ by observing $M (D)$ , given partial knowledge $ˆ B$ . Since $ˆ B$ is given to the attacker prior to $M (D)$ , we must condition the probabilities by $ˆ B$ .

Definition 56 (PLRV for partial knowledge). Given a mechanism $M$ , a distribution $θ$ with values in $D \times B$ , an index $i$ , and values $t, t^{'} \in T$ , the PLRV of an output $ˆ O \in O$ given partial knowledge $ˆ B \in B$ is:

L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (ˆ O, ˆ B) = ln \frac{P_{θ} [M (D) = ˆ O ∣ ∣ D (i) = t, B = ˆ B]}{P_{θ} [M (D) = ˆ O ∣ ∣ D (i) = t^{'}, B = ˆ B]},

using the convention $x ∕ 0 = \infty$ for all $x$ .

This PLRV captures the same idea as for classical DP: it quantifies the attacker’s information gain. If $B = D_{- i}$ , this definition is the same as the classical PLRV.

Now that we translated the concept of PLRV to account for partial knowledge, we can use it to adapt the privacy definition. The formula in Proposition 8 averages the PLRV over all possible outputs $O$ , but the PLRV with partial knowledge has a second parameter, $ˆ B$ . How should this new parameter be handled? There are at least two reasonable possibilities.

Active partial knowledge

The first option is to quantify over all possibilities for the attacker’s partial knowledge. We assume the worst: we consider the case where the attacker’s partial knowledge causes the privacy to be the greatest. This models a scenario where the attacker can not only see, but also influence the data. If the attacker can, for example, add fake users to the database, then they can choose the values associated to these new records to maximize the chances of information gain. We therefore call this option active partial knowledge, short for “partial knowledge under active attacks”.

Definition 57 (APKDP). Given a family of distributions $Θ$ , a mechanism $M$ is $(Θ, ε, δ)$ -APKDP (Active Partial Knowledge Differential Privacy) if for all distributions $θ \in Θ$ , all indices $i$ , all $t, t^{'} \in T$ , and all $ˆ B \in B$ :

E θ_{∣ ∣ D (i) = t, ˆ B}, O \sim M (D) [max (0, 1 - e^{ε - L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, ˆ B)})] \leq δ,

or, equivalently:

M {(D)}_{∣ ∣ θ, D (i) = t, ˆ B} \approx_{ε, δ} M {(D)}_{∣ ∣ θ, D (i) = t^{'}, ˆ B}^{'} .

The proof of this equivalence is the same as in Lemma 1 in [MM18], which makes it explicit that APKDP is the same as NPr in its reformulation in [BGKS13]. As shown in [TSD20], APKDP and DP coincide whenever the attacker has full knowledge (when $B = D_{- i}$ ).

With APKDP, a fixed part of the distribution can be arbitrarily determined. In Example 7, this corresponds to having the attacker control some percentage of voters. Such an active attacker can simply add many fake “Yes” votes to the database, to reach the threshold of 100: this makes the thresholding pointless. $M$ then becomes a simple counting query which does not provide privacy: with high probability, everybody votes “No”, and the only uncertainty left is over the attacker’s target.

In addition to modeling an active attacker, APKDP can also be used in scenarios where $θ$ is unknown, but can be approximated. The “partial knowledge” can represent the error between the true distribution and the approximation and if APKDP is satisfied, then the privacy property also holds for the true database.

Note that in this context, explicitly modeling the background knowledge $ˆ B$ is technically not necessary. Instead, we could simply create a new family of probability distributions $Θ^{'}$ by conditioning each $θ \in Θ$ by the value of each possible $ˆ B$ . We make this background knowledge explicit instead, so APKDP is easier to compare with PPKDP, defined in the next section.

Passive partial knowledge

APKDP represents situations where the attacker can modify the data. An example is an online service that publishes statistics about its use, where the attacker can interact with the service before the usage statistics are published. Now, what if the attacker cannot interact with the data? Consider e.g. researchers publishing the results of a clinical study about patients having a medical condition. A typical attacker cannot influence the clinical data, but might have some partial knowledge about other participants to the survey.

How can we model such a passive attacker, which has access to some information about the data, but cannot influence it? It no longer makes sense to quantify over arbitrary partial knowledge. In the same way that the reformulation of $(ε, δ)$ -DP using the PLRV averages the PLRV over all possible outputs, we must average the PLRV over all possible values of the partial knowledge.

Definition 58 (PPKDP). Given a family of distributions $Θ$ , a mechanism $M$ is $(Θ, ε, δ)$ -PPKDP (Passive Partial Knowledge Differential Privacy) if for all distributions $θ \in Θ$ , all indices $i$ , and all $t, t^{'} \in T$ :

E θ_{| D (i) = t}, O \sim M (D) [max (0, 1 - e^{ε - L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, B)})] \leq δ .

In this context, $δ$ has a similar meaning as in $(ε, δ)$ -DP: it captures the probability that the attacker is lucky. In $(ε, δ)$ -DP, it means that $O$ allows the attacker to distinguish between $D_{1}$ and $D_{2}$ with high probability, or, equivalently, that the PLRV associated to output $O$ is large. In $(ε, δ)$ -PPKDP however, $δ$ captures the probability of the attacker getting either a favorable output $O$ , or a favorable partial knowledge $B$ .

With PPKDP, the thresholding mechanism of Example 7 is private. Indeed, with high probability, the partial knowledge will have only “No” votes; and almost certainly, the mechanism will output $⊥$ and gives no information. We formalize this intuition in Section 3.2.2.

Note that as opposed to APKDP, PPKDP cannot be easily reformulated using $(ε, δ)$ -indistinguishability. Since the statement $B = ˆ B$ conditions both probabilities, the $δ$ in $(ε, δ)$ -indistinguishability only applies to the randomness of $M$ . To use an indistinguishability-based formulation, we would need to use $δ$ twice, and (for example) explicitly require that $(ε, δ)$ -indistinguishability holds with probability $1 - δ$ over the choice of $ˆ B$ .

Remark 1. PPKDP shares some characteristics with inference-based distributional differential privacy (IBDDP), introduced in [BGKS13]. A mechanism $M$ satisfies IBDDP if there is a simulator $Sim$ such that for all probability distributions $θ \in Θ$ , and indices $i$ , the statement:

\begin{matrix} {D (i)}_{∣ ∣ θ, M (D) = ˆ O, ˆ B} \approx_{ε, δ} {D (i)}_{∣ ∣ θ, Sim (D_{- i}) = ˆ O, ˆ B} \end{matrix}

holds with probability $1 - δ$ over the choice of $ˆ O$ and $ˆ B$ .

Leaving aside the simulator, note that $δ$ is used in two separate parts of the definition: both over the choice of $ˆ O$ and $ˆ B$ , and in the indistinguishability. As such, it is difficult see intuitively what $δ$ corresponds to, and the interpretation based on the “probability that the attacker gets more information than $e^{ε}$ ” is not correct. This is one of the reasons why a PLRV-based formulation is more convenient: $δ$ can simply be interpreted in the same way as in $(ε, δ)$ -differential privacy.

Further, the strict implication between DistDP and IBDDP proven in [BGKS13] can be explained by a similar distinction between an active and a passive attacker, even if it is not made explicit in the original paper. Indeed, when $δ > 0$ , this $δ$ applies only to the indistinguishability property of DistDP, and DistDP quantifies over all possible values of the background knowledge: the attacker is assumed to be able to choose the most favorable value of the background knowledge. In contrast, with IBDDP, $δ$ is applied both to the indistinguishability property and to the choice of the background knowledge; hence the attacker is implicitly assumed to get the background knowledge randomly.

Relation between definitions

In this section, we formalize the relation between PPKDP and APKDP and show basic results on those definitions.

First, APKDP and PPKDP satisfy both privacy axioms proposed in [KL10], which we reproduced in Definition 9 in Section 2.2.1. These axioms express natural properties that we expect to be true for any reasonable definition of privacy.

Proposition 25. PPKDP satisfies the post-processing axiom: if a mechanism $M$ is $(Θ, ε, δ)$ -PPKDP, then for any function $f$ , the mechanism $M^{'}$ defined by $M^{'} (D) = f (M (D))$ is also $(Θ, ε, δ)$ -PPKDP. It also satisfies the convexity axiom: if two mechanisms $M_{1}$ and $M_{2}$ are both $(Θ, ε, δ)$ -PPKDP, then the mechanism $M$ that applies $M_{1}$ with some probability $p$ and $M_{2}$ with probability $1 - p$ is also $(Θ, ε, δ)$ -PPKDP.

APKDP also satisfies these axioms.

Proof. For APKDP, the reformulation of the definition using classical $(ε, δ)$ -indistinguishability makes the result straightforward: the proof is the same as for $(ε, δ)$ -DP. For PPKDP, we first reformulate the definition using $f$ -divergence. Let $f (x) = max (0, 1 - e^{ε} x)$ . Then a mechanism $M$ is $(Θ, ε, δ)$ -PPKDP iff:

\begin{matrix} \sum_{ˆ B} P [ˆ B ∣ ∣ D (i) = t] D_{f} (M {(D)}_{∣ ∣ θ, D (i) = t, ˆ B} ∥ M {(D)}_{∣ ∣ θ, D (i) = t^{'}, ˆ B}^{'}) \leq δ . \end{matrix}

This view allows us to use the monotonicity and joint convexity properties of the $f$ -divergence to immediately prove the result for PPKDP. □

We saw that $(ε, δ)$ -APKDP bounds the probability mass of the PLRV above $ε$ by $δ$ , for all possible partial knowledge $ˆ B$ . By contrast, PPKDP bounds the same probability mass, averaged over all possible values of $ˆ B$ , weighted by their likelihood. We formalize this interpretation and use it to show that APKDP is, as expected, stronger than PPKDP. More surprisingly, we also use it to show that when $δ = 0$ , both definitions are equivalent.

Theorem 1. Given a distribution $θ$ , a mechanism $M$ , an index $i$ , two values $t, t^{'} \in T$ , an output $O$ , a possible value of the partial knowledge $ˆ B$ , and a fixed $ε > 0$ , let us denote $m (O, ˆ B) = max (0, 1 - e^{ε - L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, ˆ B)})$ . The respective quantities bounded by the requirements of APKDP and PPKDP are:

\begin{matrix} {APK}_{i, t, t^{'}, ˆ B}^{'} & = E θ_{∣ ∣ D (i) = t, ˆ B}, O \sim M (D) [m (O, ˆ B)] \end{matrix}

and:

\begin{matrix} {PPK}_{i, t, t^{'}}^{'} & = E θ_{| D (i) = t}, O \sim M (D) [m (O, B)] = E θ_{| D (i) = t} [{APK}_{i, t, t^{'}, B}^{'}] . \end{matrix}

As an immediate consequence, if $M$ is $(Θ, ε, δ)$ -APKDP, then it is also $(Θ, ε, δ)$ -PPKDP. Further, $(Θ, ε)$ -PPKDP and $(Θ, ε)$ -APKDP are equivalent.

Proof. We decompose ${PPK}_{i, t, t^{'}}^{'}$ depending the value of $B$ .

\begin{matrix} {PPK}_{i, t, t^{'}}^{'} & = \sum_{ˆ D, ˆ B} P [D = ˆ D, ˆ B ∣ ∣ D (i) = t] E O \sim M (ˆ D) [m (O, ˆ B)] = \sum_{ˆ B} P [ˆ B ∣ ∣ D (i) = t] \sum_{ˆ D} P [D = ˆ D ∣ ∣ D (i) = t, ˆ B] \cdot E O \sim M (ˆ D) [m (O, ˆ B)] = \sum_{ˆ B} P [ˆ B ∣ ∣ D (i) = t] E θ_{∣ ∣ D (i) = t, ˆ B}, O \sim M (D) [m (O, ˆ B)] = \sum_{ˆ B} P [ˆ B ∣ ∣ D (i) = t] {APK}_{i, t, t^{'}, ˆ B}^{'} = E θ_{| D (i) = t} [AP K_{i, t, t^{'}, B}^{'}] . \end{matrix}

For the second part of the statement, if the mechanism is $(ε, δ)$ -APKDP, then for all $i$ , $t$ , $t^{'}$ , and $ˆ B$ , ${APK}_{i, t, t^{'}, ˆ B}^{'} \leq δ$ , so:

\begin{matrix} {PPK}_{i, t, t^{'}}^{'} & = E θ_{| D (i) = t} [{APK}_{i, t, t^{'}, B}^{'}] \leq E θ_{| D (i) = t} [δ] \leq δ . \end{matrix}

For the last part of the statement, assume that $M$ is $(Θ, ε)$ -PPKDP. Then:

\begin{matrix} 0 = {PPK}_{i, t, t^{'}}^{'} = & E θ_{| D (i) = t} [{APK}_{i, t, t^{'}, B}^{'}] . \end{matrix}

All summands are non-negative, so the sum can only be $0$ if all summands are $0$ : for all $ˆ B$ , ${APK}_{i, t, t^{'}, ˆ B}^{'} = 0$ , and $M$ is $(Θ, ε)$ -APKDP. □

When $δ > 0$ , the implication is strict: the PLRV can be arbitrarily higher for certain values $ˆ B$ of the background knowledge. Thus, quantifying over all possible values $ˆ B$ can lead to much larger values of $ε$ and $δ$ than averaging over all possible values of the background knowledge: Example 7 illustrates this phenomenon. When $δ = 0$ however, $ε$ -APKDP and $ε$ -PPKDP are both worst-case properties, like $ε$ -DP: an attacker’s ability to choose the background knowledge does not matter, since even for the passive attacker, we need to consider the worst possible output $O$ and background knowledge $B$ .

$Θ$ -reducible mechanisms

For some mechanisms and probability distributions, active attackers are, perhaps surprisingly, not more powerful than passive attackers, even when $δ > 0$ . We introduce here a necessary condition for APKDP and PPKDP to be equivalent and we show that this condition appears in natural contexts.

Consider the example of a referendum where 2000 users take part in a vote with two options. Each user $i$ votes “yes” with probability $p_{i}$ , and “no” with probability $1 - p_{i}$ . The mechanism $M$ returns the exact tally of the vote. We assume that the attacker knows half of the votes: their partial knowledge is the vote of 1000 users. They might know that e.g. 500 of these users voted “yes”, 500 voted “no”, and the remaining 1000 votes are unknown. The attacker aims to get information on the vote of their target.

Does it matter, in this situation, whether the attacker is passive or active? If the attacker can choose the votes of 1000 users, they can decide that each known user will vote “yes”. But changing these votes will only modify the tally in a predictable way: the attacker can remove these votes from the total tally. Intuitively, it does not matter whether these known users all vote “yes”, “no”, or have any other behavior known to the attacker. Without dependency relationships between users, the attacker’s uncertainty solely resides in the unknown votes: a passive attacker is not weaker than an active attacker.

We generalize this intuition via the concept of $Θ$ -reducibility, which captures scenarios where all possible values of background knowledge are equivalent from a privacy perspective. We then show that under this condition, APKDP is equivalent to PPKDP, and formalize the above example to show that it satisfies this condition.

Definition 59 ( $Θ$ -reducibility). A mechanism $M$ is $Θ$ -reducible if for all indices $i$ , and all $B_{1}, B_{2} \in B$ , there is a bijective mapping $φ_{B_{1}, B_{2}}^{i} : O \to O$ such that for all $t \in T$ and for all $O \in O$ :

\begin{matrix} P_{θ} [M (D) = O | D (i) = t, B = B_{1}] = P_{θ} [M (D) = φ_{B_{1}, B_{2}}^{i} (O) ∣ ∣ D (i) = t, B = B_{2}] . \end{matrix}

This equivalence between possible outputs under $B_{1}$ and $B_{2}$ can be translated to an equivalence between the corresponding PLRVs: if $M$ is $Θ$ -reducible, then the global behavior of $L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} {(O, B_{1})}_{| O \sim M (D), D (i) = t}$ and of $L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} {(O, B_{2})}_{| O \sim M (D), D (i) = t}$ are the same. This equivalence between PLRVs enables us to show that $Θ$ -reducibility implies APKDP and PPKDP are the same, even when $δ > 0$ . So there are mechanisms and background knowledge functions for which an active attacker is not stronger than a passive one.

Theorem 2. Let $Θ$ be a family of probability distributions, and let $M$ be a $Θ$ -reducible mechanism. Then $M$ is $(Θ, ε, δ)$ -APKDP iff it is $(Θ, ε, δ)$ -PPKDP.

Proof. First, we show that for all $O \in O$ and all $B_{1}, B_{2} \in B$ :

L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, B_{1}) = L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (φ_{B_{1}, B_{2}} (O), B_{2}) .

This statement directly follows by unfolding the definition of $L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, B_{1})$ (Definition 56) and $Θ$ -reducibility (Definition 59):

\begin{matrix} L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, B_{1}) & = ln \frac{P_{θ} [M (D) = O | D (i) = t, B = B_{1}]}{P_{θ} [M (D) = O ∣ ∣ D (i) = t^{'}, B = B_{1}]} = ln \frac{P_{θ} [M (D) = φ_{B_{1}, B_{2}} (O) ∣ ∣ D (i) = t, B = B_{2}]}{P_{θ} [M (D) = φ_{B_{1}, B_{2}} (O) ∣ ∣ D (i) = t^{'}, B = B_{2}]} = L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (φ_{B_{1}, B_{2}} (O), B_{2}) . \end{matrix}

We can now prove Theorem 2. Since ${APK}_{i, t, t^{'}}^{'}$ is the expected value of ${PPK}_{i, t, t^{'}, B}^{'}$ (Theorem 1), it is enough to prove that for any $B_{1}$ and $B_{2}$ , ${APK}_{i, t, t^{'}, B_{1}}^{'} = {APK}_{i, t, t^{'}, B_{2}}^{'}$ . Recall that $m (O, B) = max (0, 1 - e^{ε - L_{i \leftarrow t / i \leftarrow t^{'}}^{M, θ} (O, B)})$ , and fix $B_{1}$ and $B_{2}$ in $B$ . We have:

\begin{matrix} {APK}_{i, t, t^{'}, B_{1}}^{'} & = \sum_{ˆ O} P [M (D) = ˆ O ∣ ∣ D (i) = t, B = B_{1}] m (ˆ O, B_{1}) = \sum_{ˆ O} P [M (D) = φ_{B_{1}, B = B_{2}} (ˆ O) ∣ ∣ D (i) = t, B = B_{2}] m (φ_{B_{1}, B_{2}} (ˆ O), B_{2}) \end{matrix}

using Definition 59 and the technical result above. We can then reindex the sum using the bijection $ˆ O \to φ_{B_{1}, B_{2}} (ˆ O)$ , and conclude:

\begin{matrix} {APK}_{i, t, t^{'}, B_{1}}^{'} & = \sum_{ˆ O} P [M (D) = ˆ O ∣ ∣ D (i) = t, B = B_{2}] m (ˆ O, B_{2}) = {APK}_{i, t, t^{'}, B_{2}}^{'} . \end{matrix}

□

$Θ$ -reducible mechanisms are fairly common, especially under the natural assumption that the attacker knows a fixed part of the dataset. We give a few examples.

Proposition 26. Let $Θ$ be a family of distributions in which each $θ$ generates the record of each user independently, and assume that the background knowledge of the attacker is $k$ fixed records of the database, for a given $k$ . Then the following mechanisms are $Θ$ -reducible.

1.: Counting queries: given a predicate $P$ , the algorithm’s output is the number of records for which $P (D (i))$ is true. This a generalizes binary voting.
2.: Linear queries: given a fixed family of weights $(α_{i})$ , the mechanism returns $\sum_{i} α_{i} D (i)$ .
3.: Different types of means: the arithmetic mean, the geometric mean, the harmonic mean, and the quadratic mean (assuming all $D (i)$ are positive).

Proof. Fix $θ \in Θ$ . For counting queries, given $B_{1}, B_{2} \in B$ , define $φ_{B_{1}, B_{2}, i}^{count} (M (D)) = M (D) - M (B_{1}) + M (B_{2})$ . This function is linear, so injective. Call $θ^{'}$ the random distribution of the $n - k$ records not present in $B$ . Then for all $a \in T$ and all $O \in O$ :

\begin{matrix} P_{θ} [M (D) = O | D (i) = t, B = B_{1}] & = P_{D^{'} \sim θ^{'}}^{'} [M (D^{'} \cup B_{1}) = O ∣ ∣ {(D^{'} \cup B_{1})}_{i}^{'} = t] = P_{D^{'} \sim θ^{'}}^{'} [M (D^{'} \cup B_{2}) = φ_{B_{1}, B_{2}, i}^{count} (O) ∣ ∣ {(D^{'} \cup B_{2})}_{i}^{'} = t] = P_{θ} [M (D) = φ_{B_{1}, B_{2}, i}^{count} (O) ∣ ∣ D (i) = t, B = B_{2}] . \end{matrix}

For linear queries, we use a similar mapping to $φ$ , which also depends on the mapping. Let $I$ be the indices of records present in $B$ ; then a linear query is $Θ$ -reducible with:

\begin{matrix} φ_{B_{1}, B_{2}, i}^{linear} (M (D)) = M (D) + \sum_{j \in I} α_{j} ({(B_{2})}_{j} - {(B_{1})}_{j}) . \end{matrix}

This also proves the result for the arithmetic mean.

Similarly, it is easy to verify that the following $φ$ functions show $Θ$ -reducibility for the geometric, harmonic and quadratic mean.

\begin{matrix} φ_{B_{1}, B_{2}, i}^{geometric} (M (D)) = {(M {(D)}^{n} \cdot \frac{\prod_{j \in I} {(B_{2})}_{j}}{\prod_{j \in I} {(B_{1})}_{j}})}^{1 ∕ n} φ_{B_{1}, B_{2}, i}^{harmonic} (M (D)) = n {({(\frac{M (D)}{n})}^{- 1} + \sum_{j} (\frac{1}{{(B_{2})}_{j}} - \frac{1}{{(B_{1})}_{j}}))}^{- 1} φ_{B_{1}, B_{2}, i}^{quadratic} (M (D)) = \sqrt{n \cdot M {(D)}^{2} + \sum_{j} \frac{{(B_{2})}_{j}^{2} - {(B_{1})}_{j}^{2}}{n}} \end{matrix}

The injectivity of each of these functions is clear. □

Note that in Proposition 26, it is crucial that the records in the attacker’s partial knowledge are fixed. In general, knowing the records of $k$ users is not equivalent to knowing the records of $k$ other users. Indeed, if these records are generated with different probabilities, the randomness from the unknown records differs between both scenarios, and it is in general impossible to convert one into the other.

Remark 2. Observation 1 in [GK17b] claims that the partial knowledge of $k$ records in a database of size $n$ is the same as no partial knowledge in a database of size $n - k$ . For counting queries, this holds for the same reason that counting queries are $Θ$ -reducible: one can “remove” the $k$ known records from the mechanism output and obtain a bijection between the cases with and without partial knowledge. Thus, the partial knowledge is irrelevant to the mechanism’s privacy and can be ignored.

This observation, however, does not hold in general: we later show in Example 7 that counting queries with thresholding are not $Θ$ -reducible, and in this case, the knowledge of $k$ records in a database of size $n$ has a very different effect than no partial knowledge in a database of size $n - k$ .

LINKPREV LINKUP LINKNEXT