Data Sanitisation Protocols for the Privacy Funnel with Differential Privacy Guarantees

This paper is an extended version of [18]. Under the Open Data paradigm, governments and other public organisations want to share their collected data with the general public. This increases a government’s transparency, and it also gives citizens and businesses the means to participate in decision-making, as well as using the data for their own purposes. However, while the released data should be as faithful to the raw data as possible, individual citizens’ private data should not be compromised by such data publication.

Let $\mathcal{X}$ be a finite set. Consider a database $\vec{X}=(X_{1},\ldots,X_{n})\in\mathcal{X}^{n}$ owned by a data aggregator, containing a data item $X_{i}\in\mathcal{X}$ for each user $i$ (For typical database settings, each user’s data is a vector of attributes $X_{i}=(X_{i}^{1},\ldots,X_{i}^{m})$; we will consider this in more detail in Section V). This data may not be considered sensitive by itself, but it might be correlated to a secret $S_{i}$. For instance, $X_{i}$ might contain the age, sex, weight, skin colour, and average blood pressure of person $i$, while $S_{i}$ is the presence of some medical condition. To publish the data without leaking the $S_{i}$, the aggregator releases a privatised database $\vec{Y}=(Y_{1},\ldots,Y_{n})$, obtained from applying a sanitisation mechanism $\mathcal{R}$ to $\vec{X}$. One way to formulate this is by considering the Privacy Funnel:

There are two difficulties with this approach:

1. 1.

   Finding and implementing good privatization mechanisms that operate on all of $\vec{X}$ can be computationally prohibitive for large $n$, as the complexity is exponential in $n$ [6][22].

2. 2.

   Taking mutual information as a leakage measure has as a disadvantage that it gives guarantees about the leakage in the average case. If $n$ is large, this still leaves room for the sanitisation protocol to leak undesirably much information about a few unlucky users.

To deal with these two difficulties, we make two changes to the general approach. First, we look at local data sanitisation, i.e., we consider optimization protocols $\mathcal{Q}\colon\mathcal{X}\rightarrow\mathcal{Y}$, for some finite set $\mathcal{Y}$, and we apply $\mathcal{Q}$ to each $X_{i}$ individually; this situation is depicted in Figure 1. Local sanitisation can be implemented efficiently. In fact, this approach is often taken in the Privacy Funnel setting [20][6]. Second, to ensure strong privacy guarantees even in worst-case scenarios, we take stricter notions of privacy, based on Local Differential Privacy (LDP) [15]. For these metrics, we develop methods to find optimal protocols. Furthermore, for situations where the optimal protocol is computationally unfeasible to find, we introduce a new protocol, Conditional Reporting (CR), that takes advantage of the fact that only $S_{i}$ needs to be protected. Determining CR only requires finding the root of a onedimensional increasing function, which can be done fast numerically.

The database $\vec{X}=(X_{1},\ldots,X_{n})$ consists of a data item $X_{i}$ for each user $i$, each an element of a given finite set $\mathcal{X}$. Furthermore, each user has sensitive data $S_{i}\in\mathcal{S}$, which is correlated with $X_{i}$; again we assume $\mathcal{S}$ to be finite (see Figure 1). We assume that each $(S_{i},X_{i})$ is drawn independently from the same distribution $\operatorname{p}_{S,X}$ on $\mathcal{S}\times\mathcal{X}$ which is known to the aggregator through observing $(\vec{S},\vec{X})$ (if one allows for non-independent $X_{i}$, then differential privacy is no longer an adequate privacy metric [5][24]). The aggregator, who has access to $\vec{X}$, sanitises the database by applying a sanitisation protocol (i.e., a random function) $\mathcal{Q}\colon\mathcal{X}\rightarrow\mathcal{Y}$ to each $X_{i}$, outputting $\vec{Y}=(Y_{1},\ldots,Y_{n})=(\mathcal{Q}(X_{1}),\ldots,\mathcal{Q}(X_{n}))$. The aggregator’s goal is to find a $\mathcal{Q}$ that maximises the information about $X_{i}$ preserved in $Y_{i}$ (measured as $\operatorname{I}(X_{i};Y_{i})$) while leaking only minimal information about $S_{i}$.

Without loss of generality we write $\mathcal{X}=\{1,\ldots,a\}$, $\mathcal{Y}=\{1,\ldots,b\}$ and $\mathcal{S}=\{1,\ldots,c\}$ for integers $a,b,c$. We omit the subscript $i$ from $X_{i}$, $Y_{i}$, $S_{i}$ as no probabilities depend on it, and we write such probabilities as $\operatorname{p}_{x}$, $\operatorname{p}_{s}$, $\operatorname{p}_{x|s}$, etc., which form vectors $\operatorname{p}_{X}$, $\operatorname{p}_{S|x}$, etc., and matrices $\operatorname{p}_{X|S}$, etc.

As noted before, instead of looking at the mutual information $\operatorname{I}(S;Y)$, we consider two different, related measures of sensitive information leakage known from the literature. The first one is an adaptation of LDP, the de facto standard in information privacy [15]:

Most literature on LDP considers LDP w.r.t. $X$, i.e. $\frac{\mathbb{P}(Y=y|X=x)}{\mathbb{P}(Y=y|X=x^{\prime})}\leq\textrm{e}^{\varepsilon}$ for all $x,x^{\prime},y$. Throughout this paper, by $\varepsilon$-LDP we always mean $\varepsilon$-LDP w.r.t. $S$, unless otherwise specified.

The LDP metric reflects the fact that we are only interested in hiding sensitive data, rather than all data; it is a specific case of what has been named ‘pufferfish privacy’ [16]. The advantage of LDP compared to mutual information is that it gives privacy guarantees for the worst case, not just the average case. This is desirable in the database setting, as a worst-case metric guarantees the security of the private data of all users, while average-case metrics are only concerned with the average user. Another useful privacy metric is Local Information Privacy (LIP) [13][24], also called Removal Local Differential Privacy [11]:

Compared to LDP, the disadvantage of LIP is that it depends on the distribution of $S$; this is not a problem in our scenario, as the aggregator, who chooses $\mathcal{Q}$, has access to the distribution of $S$. The advantage of LIP is that is more closely related to an attacker’s capabilities: since $\frac{\mathbb{P}(Y=y|S=s)}{\mathbb{P}(Y=y)}=\frac{\mathbb{P}(S=s|Y=y)}{\mathbb{P}(S=s)}$, satisfying $\varepsilon$-LIP means that an attacker’s posterior distribution of $S$ given $Y=y$ does not deviate from their prior distribution by more than a factor $\textrm{e}^{\varepsilon}$. The following lemma outlines the relations between LDP, LIP and mutual information (see Figure 2).

In this notation, instead of Problem 1 we consider the following problem:

Note that this problem does not depend on the number of users $n$, and as such this approach will find solutions that are scalable w.r.t. $n$.

Our goal is now to find the optimal $\mathcal{Q}$, i.e., the protocol that maximises $\operatorname{I}(X;Y)$ while satisfying $\varepsilon$-LDP, for a given $\varepsilon$. We can represent any sanitisation protocol as a matrix $Q\in\mathbb{R}^{b\times a}$, where $Q_{y|x}=\mathbb{P}(Y=y|X=x)$. Then, $\varepsilon$-LDP is satisfied if and only if

As such, for a given $\mathcal{Y}$, the set of $\varepsilon$-LDP-satisfying sanitisation protocols can be considered a closed, bounded, convex polytope $\Gamma$ in $\mathbb{R}^{b\times a}$. This fact allows us to efficiently find optimal protocols.

This theorem reduces the search for the optimal LDP protocol to enumerating the set of vertices of $\Gamma$, a $a(a-1)$-dimensional convex polytope.

One might argue that, since the optimal $\mathcal{Q}$ depends on $\operatorname{p}_{S,X}$, the publication of $\mathcal{Q}$ might provide an aggregator with information about the distribution of $S$. However, information on the distribution (as opposed to information of individual users’ data) is not considered sensitive [19]. In fact, the reason why the aggregator sanitises the data is because an attacker is assumed to have knowledge about this correlation, and revealing too much information about $X$ would cause the aggregator to use this information to infer information about $S$.

If one uses $\varepsilon$-LIP as a privacy metric, one can find the optimal sanitisation protocol in a similar fashion. To do this, we again describe $\mathcal{Q}$ as a matrix, but this time a different one. Let $q\in\mathbb{R}^{b}$ be the probability mass function of $Y$, and let $R\in\mathbb{R}^{a\times b}$ be given by $R_{x|y}=\mathbb{P}(X=x|Y=y)$; we denote its $y$-th row by $R_{X|y}\in\mathbb{R}^{a}$. Then, a pair $(R,q)$ defines a sanitisation protocol $\mathcal{Q}$ satisfying $\varepsilon$-LIP if and only if

Note that (10) defines the $\varepsilon$-LIP condition, since for a given $s,y$ we have $\frac{\operatorname{p}_{s|X}R_{X|y}}{\operatorname{p}_{S}}=\frac{\mathbb{P}(S=s|Y=y)}{\mathbb{P}(S=s)}=\frac{\mathbb{P}(Y=y|S=s)}{\mathbb{P}(Y=y)}$. (In)equalities (8–10) can be expressed as saying that for every $y\in\mathcal{Y}$ one has that $R_{X|y}\in\Delta$, where $\Delta$ is the convex closed bounded polytope in $\mathbb{R}^{\mathcal{X}}$ given by

As in Theorem 2, we can use this polytope to find optimal protocols:

Since linear optimization problems can be solved fast, again the optimization problem reduces to finding the vertices of a polytope. The advantage of using LIP instead of LDP is that $\Delta$ is a $(a-1)$-dimensional polytope, while $\Gamma$ of Section III is $a(a-1)$-dimensional. The time complexity of vertex enumeration is linear in the number of vertices [1], while the number of vertices can grow exponentially in the dimension of the polyhedron [2]. Together, this means that the dimension plays a huge role in the time complexity, hence we expect finding the optimum under LIP to be significantly faster than under LDP.

An often-occuring scenario is that a user’s data consists of multiple attributes, i.e., $X=(X^{1},\ldots,X^{m})\in\mathcal{X}=\mathcal{X}^{1}\times\cdots\times\mathcal{X}^{m}$. This can be problematic for our approach for two reasons:

1. 1.

   Such a large $\mathcal{X}$ can be problematic, since the computing time for optimisation both under LDP and LIP will depend heavily on $a$.

2. 2.

   In practice, an attacker might sometimes utilise side channels to access some subsets of attributes $X_{i}^{j}$ for some users. For these users, a sanitisation protocol can leak more information (w.r.t. to the attacker’s updated prior information) than its LDP/LIP parameter would suggest.

To see how the second problem might arise in practice, suppose that $X^{1}_{i}$ is the height of individual $i$, $X^{2}_{i}$ is their weight, and $S_{i}$ is whether $i$ is obese or not. Since height is only lightly correlated with obesity, taking $Y_{i}=X_{i}^{1}$ would satisfy $\varepsilon$-LIP for some reasonably small $\varepsilon$. However, suppose that an attacker has access to $X^{2}_{i}$ via a side channel. While knowing $i$’s weight gives the attacker some, but not perfect knowledge about $i$’s obesity, the combination of the weight from the side channel, and the height from the $Y_{i}$, allows the attacker to calculate $i$’s BMI, giving much more information about $i$’s obesity. Therefore, the given protocol gives much less privacy in the presence of this side channel.

To solve the second problem, we introduce a more stringent privacy notion called Side-channel Resistant LIP (SRLIP), which ensures that no matter which attributes an attacker has access to, the protocol still satisfies $\varepsilon$-LIP with respect to the attacker’s new prior distribution. One could similarly introduce SRLDP, and many results will still hold for this privacy measure; nevertheless, since we concluded that LIP is preferable to LDP, we focus on SRLIP. For any subset $J\subseteq\{1,\ldots,m\}$, we write $\mathcal{X}^{J}=\prod_{j\in J}\mathcal{X}^{j}$ and its elements as $x^{J}$.

In terms of Remark 1, $\mathcal{Q}$ satisfies $\varepsilon$-SRLIP if and only if it satisfies $\varepsilon$-LIP w.r.t. $\operatorname{p}_{S,X|x^{J}}$ for all $J$ and $x^{J}$. Taking $J=\varnothing$ gives us the regular definition of $\varepsilon$-LIP, proving the following Lemma:

While SRLIP is stricter than LIP itself, it has the advantage that even when an attacker has access to some data of a user, the sanitisation protocol still does not leak an unwanted amount of information beyond the knowledge the attacker has gained via the side channel. Another advantage is that, contrary to LIP itself, SRLIP satisfies an analogon of the concept of privacy budget [9]:

The proof is presented in Appendix A. This theorem tells us that to find a $\varepsilon$-SRLIP protocol for $\mathcal{X}$, it suffices to find a sanitisation protocol for each $\mathcal{X}^{j}$ that is $\frac{\varepsilon}{m}$-LIP w.r.t. a number of prior distributions. Unfortunately, the method of finding an optimal $\varepsilon$-LIP protocol w.r.t. one prior $\operatorname{p}_{S,X}$ of Theorem 3 does not transfer to the multiple prior setting. This is because this method only finds one $(R,q)$, while by (7) we need a different $(R,q)$ for each prior distribution. Therefore, we are forced to adopt an approach similar to the one in Theorem 2. The matrix $Q^{j}$ (given by $Q^{j}_{y^{j}|x^{j}}=\mathbb{P}(\mathcal{Q}^{j}(x^{j})=y^{j}$)) corresponding to $\mathcal{Q}^{j}\colon\mathcal{X}^{j}\rightarrow\mathcal{Y}^{j}$ satisfies the criteria of Theorem 4 if and only if the following criteria are satisfied:

Similar to Theorem 2, we can find the optimal $\mathcal{Q}^{j}$ satisfying these conditions by finding the vertices of the polytope defined by (20–23). In terms of time complexity, the comparison to finding the optimal $\varepsilon$-LIP protocol via Theorem 3 versus finding a $\varepsilon$-SRLIP protocol via Theorem 4 is not straightforward. The complexity of enumerating the vertices of a polytope is $\mathcal{O}(ndv)$, where $n$ is the number of inequalities, $d$ is the dimension, and $v$ is the number of vertices [1]. For the $\Delta$ of Theorem 3 we have $d=a-1$ and $n=a+2c$. In contrast, the polytope defined by (20–23) satisfies $d=a^{j}(a^{j}-1)$ and $n=(a^{j})^{2}+2c\prod_{j^{\prime}\neq j}(a^{j^{\prime}}+1)$. Finding $v$ for both these polytopes is difficult, but in general $v\leq\binom{n}{d}$. Since this grows exponentially in $d$, we expect Theorem 4 to be faster when the $a^{j}$ are small compared to $a$, i.e., when $m$ is large. We will investigate this experimentally in the next section.

The methods of Sections III and IV allow us to find the optimal LDP and LIP protocols. The complexity depends heavily on $a$ and $c$, and can become computationally infeasible for large $a$ and $c$. For such datasets, one has to rely on predetermined privacy algorithms. We consider two approaches: as a benchmark, we discuss how ‘standard’ LDP protocols can be applied to the Privacy Funnel situation, and we introduce a new method, Conditional Reporting, that is meant to address the shortcomings of standard LDP protocols. As in the previous section, we focus on LIP, but much of the discussion carries over to LDP as well.

We test the feasibility of the different methods by performing small-scale experiments on synthetic data and real-world data. All experiments are implemented in Matlab and conducted on a PC with Intel Core i7-7700HQ 2.8GHz and 32GB memory.

Local data sanitisation protocols have the advantage of being scalable for large numbers of users. Furthermore, the advantage of using differential privacy-like privacy metrics is that they provide worst-case guarantees, ensuring that the privacy of every user is sufficiently protected. For both $\varepsilon$-LDP and $\varepsilon$-LIP we have derived methods to find optimal sanitisation protocols. Within this setting, we have observed that $\varepsilon$-LIP has two main advantages over $\varepsilon$-LDP. First, it fits better within the privacy funnel setting, where the distribution $\operatorname{p}_{S,X}$ is (at least approximately) known to the estimator. Second, finding the optimal protocol is significantly faster than under LDP, especially for small $\varepsilon$. If one nevertheless prefers $\varepsilon$-LDP as a privacy metric, then it is still worthwile to find the optimal $\frac{\varepsilon}{2}$-LIP protocol, as this can be found significantly faster, at a low utility penalty.

In the multiple attributes setting, we have shown that $\varepsilon$-SRLIP provides additional privacy guarantees compared to $\varepsilon$-LIP, since without this requirement a protocol can lose all its privacy protection in the presence of side channels. Unfortunately, however, experiments show that we pay for this both in computation time and in utility.

With regard to the specific protocols, we have found that the newly introduced protocol, CR, generally outperforms OUE, especially for high values of $\varepsilon$-LIP. It behaves more or less similar to GRR, and which of these two protocols performs best depends on properties of the joint distribution $\operatorname{p}_{X,S}$. In particular, it largely depends on which of the two protocols has the highest value of their governing parameter $\alpha$. Also, we have seen that CR performs better on average if $a$ is large compared to $c$.

For further research, a number of important avenues remain to be explored. First, the aggregator’s knowledge about $\operatorname{p}_{S,X}$ may not be perfect, because they may learn about $\operatorname{p}_{S,X}$ through observing $(\vec{S},\vec{X})$. Incorporating this uncertainty leads to robust optimisation [3], which would give stronger privacy guarantees.

Second, it might be possible to improve the method of obtaining $\varepsilon$-SRLIP protocols via Theorem 4. Examining its proof shows that lower values of $\varepsilon^{j}$ may suffice to still ensure $\varepsilon$-SRLIP. Furthermore, the optimal choice of $(\varepsilon^{j})_{j\leq m}$ such that $\sum_{j}\varepsilon^{j}=\varepsilon$ might not be $\varepsilon^{j}=\frac{\varepsilon}{m}$. However, it is computationally prohibitive to perform the vertex enumeration for many different choices of $(\varepsilon^{j})_{j\leq m}$, and as such a new theoretical approach is needed to determine the optimal $(\varepsilon^{j})_{j\leq m}$ from $\varepsilon$ and $\operatorname{p}_{S,X}$.

Third, it would be interesting to see if there are other ways to close the gap between the theoretically optimal protocol, which may be hard to compute in practice, and general LDP protocols, which do not see the difference between sensitive and non-sensitive information. This is relevant because CR needs both $S$ and $X$ as input, and there may be situations where access to $S$ is not available.

Although CR outperforms GRR and OUE for some datasets, it does not do so consistently. More research in the properties of distributions where CR fails to provide a significant advantage might lead to improved privacy protocols.

This work was supported by NWO grant 628.001.026 (Dutch Research Council, the Hague, the Netherlands).