On the Lift, Related Privacy Measures, and Applications to Privacy–Utility Trade-Offs ^†

Abstract

This paper investigates lift, the likelihood ratio between the posterior and prior belief about sensitive features in a dataset. Maximum and minimum lifts over sensitive features quantify the adversary’s knowledge gain and should be bounded to protect privacy. We demonstrate that max- and min-lifts have a distinct range of values and probability of appearance in the dataset, referred to as lift asymmetry. We propose asymmetric local information privacy (ALIP) as a compatible privacy notion with lift asymmetry, where different bounds can be applied to min- and max-lifts. We use ALIP in the watchdog and optimal random response (ORR) mechanisms, the main methods to achieve lift-based privacy. It is shown that ALIP enhances utility in these methods compared to existing local information privacy, which ensures the same (symmetric) bounds on both max- and min-lifts. We propose subset merging for the watchdog mechanism to improve data utility and subset random response for the ORR to reduce complexity. We then investigate the related lift-based measures, including ${\ell }_1$-norm, ${\chi }^2$-privacy criterion, and $\alpha$-lift. We reveal that they can only restrict max-lift, resulting in significant min-lift leakage. To overcome this problem, we propose corresponding lift-inverse measures to restrict the min-lift. We apply these lift-based and lift-inverse measures in the watchdog mechanism. We show that they can be considered as relaxations of ALIP, where a higher utility can be achieved by bounding only average max- and min-lifts.

1. Introduction

With the recent emergence of “Big-Data”, generating, sharing, and analysing data are proliferating via the advancement of communication systems and machine learning methods. While sharing datasets is essential to achieve social and economic benefits, it may lead to the leakage of private information, which has raised great concern about the privacy preservation of individuals. The main approach to protect privacy is perturbing the data via a privacy mechanism. Consider some raw data denoted by random variable X and some sensitive features denoted by S, which are correlated via a joint distribution $P_{SX}\ne P_S\times P_X$. A privacy mechanism (characterised by the transition probability $P_{Y|X}$) is applied to publish Y as a sanitised version of X to protect S.

The design of a privacy mechanism depends on the privacy measure. Differential privacy (DP) [1,2,3] is a widely used notion of privacy. DP restricts the chance of revealing the individual’s presence in a dataset from the outcome of analysis over that dataset [4]. It ensures that neighboured sensitive features s and $s^{\prime }$, which differ in only one entry, result in a similar output probability distribution, by restricting the ratio between posterior beliefs $P_{Y|S}\left(y\right|s)/P_{Y|S}\left(y\right|s^{\prime })$ below a threshold ${\mathrm{e}}^{\epsilon }.$ The neighbourhood assumption is relaxed in the local differential privacy (LDP) [5,6,7,8,9], where the ratio between posterior beliefs is restricted below ${\mathrm{e}}^{\epsilon }$ for any two sensitive features s and $s^{\prime }$, denoted by $\epsilon$-LDP. The quantity of $\epsilon$ is known as the privacy budget. DP and LDP are considered context-free privacy notions, i.e., they do not take into account the prior distribution $P_S$. In contrast, in information-theoretic (IT) privacy, also known as context-aware privacy [10,11], it is assumed that the distribution of data or an estimation of them is available. Some of the dominant IT privacy measures are mutual information (MI) [10,12,13], maximal leakage [14,15,16], $\alpha$-leakage [17], and local information privacy (LIP) [11,18,19,20,21,22,23,24,25,26,27,28]. A challenge is that while data perturbation restricts privacy leakage, it necessarily reduces data resolution and datasets’ usefulness. Therefore, a privacy mechanism is desired to deliver a satisfactory level of data utility. Depending on the application, data utility is quantified either by measures of similarity between X and Y, such as f-divergence [7] and MI [7,12], or measures of dissimilarity and error, such as Hamming distortion [8,9] and mean square error [22], respectively. This tension between privacy and utility is known as the privacy–utility trade-off (PUT).

In this paper, we consider lift, a pivotal element in IT privacy measures, which is the likelihood ratio between the posterior belief $P_{S|Y}\left(s\right|y)$ and prior belief $P_S\left(s\right)$ about sensitive features in a dataset:

$$l(s,y)=\frac{P_{S|Y}\left(s\right|y)}{P_S\left(s\right)}=\frac{P_{SY}(s,y)}{P_S\left(s\right)P_Y\left(y\right)}.$$

(1)

The logarithm of the lift $i(s,y)=logl(s,y)$, which we call log-lift, is the information density [24]. For each y, the more $P_{S|Y}\left(s\right|y)$ differs from $P_S\left(s\right)$, the more the adversary gains knowledge about s [29]. Consequently, both min-lift and max-lift, denoted by ${min}_{s}l(s,y)$ and ${max}_{s}l(s,y)$, respectively, quantify the highest privacy leakage for each y. In [29], the role of min-lift and max-lift in privacy breach was proposed, based on which information privacy was introduced in [18]. Accordingly, min-lift is associated with revealing what values are less probable for s after observing y, while max-lift is associated with the more probable values. In addition, recently, other operational meanings for max-lift have been revealed in guessing frameworks [30] and quantitative information flow [31]. In LIP, min-lift and max-lift are bounded below and above by thresholds ${\mathrm{e}}^{-\epsilon }$ and ${\mathrm{e}}^{\epsilon }$, respectively, to restrict the adversary’s knowledge gain, denoted by $\epsilon$-LIP. The main privacy mechanisms to achieve $\epsilon$-LIP are the watchdog mechanism [24,25] and optimal random response (ORR) [28]. Watchdog mechanism bipartitions the alphabet of X into low-risk and high-risk symbols, and only high-risk ones are randomised. It was proved in [25] that X-invariant randomisation (e.g., merging all high-risk symbols) minimises privacy leakage for the watchdog mechanism. ORR is an optimal mechanism for $\epsilon$-LIP, which maximises MI as the utility measure.

Contributions

We investigate lift and its related privacy notions such as LIP. We demonstrate that min-lift and max-lift have distinct values and probability of appearance in the dataset. More specifically, min-lifts have a broader range of values than max-lifts, while max-lifts have a higher likelihood $P_{SY}(s,y)$ of appearing in the dataset. We call this property lift asymmetry. However, $\epsilon$-LIP allocates symmetric privacy budgets to ${min}_{s}i(s,y)$ and ${max}_{s}i(s,y)$ ($-\epsilon$ and $\epsilon$, respectively), which is incompatible with the lift asymmetry. Thus, we propose asymmetric-LIP (ALIP) as an amenable privacy notion to the lift properties, where asymmetric privacy budgets can be allocated to ${min}_{s}i(s,y)$ and ${max}_{s}i(s,y)$, denoted by $-{\epsilon }_l$ and ${\epsilon }_u$, respectively. We demonstrate that ALIP implies $\epsilon$-LDP and can result in better utility than LIP in the watchdog and ORR mechanisms. Utility increases by relaxing the bound on the min-lift, which has a lower probability of appearance in the dataset.

We propose two randomization methods to overcome the low utility of the watchdog mechanism and the high complexity of the ORR mechanism. In the watchdog mechanism, X-invariant randomisation perturbs all high-risk symbols together and deteriorates data resolution and utility. On the other hand, ORR suffers from high complexity, which is exponential in the size of datasets. To overcome these problems, we propose subset merging and subset random response (SRR) perturbation methods that make finer subsets of high-risk symbols and privatise each subset separately. Subset merging enhances utility in the watchdog mechanism by applying X-invariant randomisation to disjoint subsets of high-risk symbols. In addition, SRR relaxes the complexity of ORR for large datasets by applying random response solutions on disjoint subsets of high-risk symbols, which results in near-optimal utility.

Besides LIP, we also consider some recently proposed privacy measures, which we call lift-based measures, including ${\ell }_1$-norm [32], ${\chi }^2$-strong privacy [33], and $\alpha$-lift [34]. They have been proposed as the privacy notions stronger than their corresponding average leakages: the total variation distance [35], ${\chi }^2$-divergence [36], and Sibson MI [16,34], respectively. We clarify that they only bound max-lift leakage and can cause significant min-lift leakage. Therefore, we propose a corresponding modified version of these measures to restrict min-lift leakage, which we call lift-inverse measures. We apply lift-based and lift-inverse measures in the watchdog mechanism with subset merging randomisation to investigate their PUT. They result in higher utility than ALIP since they are functions of average lift over sensitive features and, thus, can be considered as relaxations of the max- and min-lift.

2. Preliminaries

2.1. Notation

We use the following notation throughout the paper. Capital letters denote discrete random variables, corresponding capital calligraphic letters denote their finite supports, and lowercase letters denote any of their realisations. For example, a random variable X has the support $\mathcal{X},$ and its realisation is $x\in \mathcal{X}$. For random variables S and X, we use $P_{SX}$ to indicate their joint probability distribution, $P_{S|X}$ for the conditional distribution of S given X, and $P_S$ and $P_X$ for the marginal distributions. Bold capital and lowercase letters are used for matrices and vectors, respectively, and lowercase letters for the corresponding elements of the vectors, e.g., $\mathbf{v}={[v_1,v_2,\cdots ,v_n]}^T$. We also use $|·|$ for the cardinality of a set, e.g., $\left|\mathcal{X}\right|$. We denote the natural logarithm by log and the set of integers $\{1,2,\cdots ,n\}$ by $\left[n\right]$. The indicator function is shown by ${\mathbf{1}}_{\left\{f\right\}}$, which is 1 when f is true and zero otherwise.

2.2. System Model and Privacy Measures

Consider some useful data intended for sharing and denoted by random variable X with alphabet $\mathcal{X}$. It is correlated with some sensitive features S with the alphabet $\mathcal{S}$ through a discrete joint distribution $P_{SX}$. To protect the sensitive features, a privacy mechanism is applied to generate a sanitised version of X, denoted by Y with the alphabet $\mathcal{Y}$. We assume $P_S$ and $P_X$ have full support, and $P_{Y|X,S}\left(y\right|x,s)=P_{Y|X}\left(y\right|x)$, which results in the Markov chain $S-X-Y$.

The main privacy measure is lift (since we assume $P_S$ and $P_Y$ have full supports, $l(s,y)$ is finite), given in (1). Lift and its logarithm, log-lift, quantify multiplicative information gain on each sensitive feature $s\in \mathcal{S}$ via accessing $y\in \mathcal{Y}$. There are two cases: $l(s,y)>1\Rightarrow P_{S|Y}\left(s\right|y)>P_S\left(s\right)$ indicates the increment of the belief about s after releasing y; $l(s,y)\le 1\Rightarrow P_{S|Y}\left(s\right|y)\le P_S\left(s\right)$ means that releasing y decreases the belief. The more the posterior belief deviates from the prior belief, the more an adversary gains knowledge about s. Thus, for each $y\in \mathcal{Y}$, the ${max}_{s}l(s,y)$ and ${min}_{s}l(s,y)$ determine the highest knowledge gain of sensitive features, and they should be restricted to protect privacy. We use the following notation for these quantities:

$$\mathsf{\Psi }\left(y\right)\triangleq \underset{s\in \mathcal{S}}{min}l(s,y)\mathrm{and}\mathsf{\Lambda }\left(y\right)\triangleq \underset{s\in \mathcal{S}}{max}l(s,y).$$

(2)

In Appendix A, we explain the operational meaning of $\mathsf{\Psi }\left(y\right)$ and $\mathsf{\Lambda }\left(y\right)$ in privacy breach based on the work in [29].

The lift has been applied in local information privacy [24,25,28] to provide protection of sensitive features, and is defined as follows.

Definition 1.

For $\epsilon \in {\mathbb{R}}_{+}$, a privacy mechanism $\mathcal{M}:\mathcal{X}\to \mathcal{Y}$ is ε-local information private or ε-LIP, with respect to S, if for all $y\in \mathcal{Y}$,

$${\mathrm{e}}^{-\epsilon }\le \mathsf{\Psi }\left(y\right)\mathit{and}\mathsf{\Lambda }\left(y\right)\le {\mathrm{e}}^{\epsilon }.$$

(3)

Another instance-wise measure is local differential privacy [5,6,28],

Definition 2.

For $\epsilon \in {\mathbb{R}}_{+}$, a privacy mechanism $\mathcal{M}:\mathcal{X}\to \mathcal{Y}$ is ε-local differential private or ε-LDP, with respect to S, if for all $s,s^{\prime }\in \mathcal{S}$ and all $y\in \mathcal{Y}$,

$$\mathsf{\Gamma }\left(y\right)=\underset{s,s^{\prime }\in \mathcal{S}}{sup}\frac{P_{Y|S}\left(y\right|s)}{P_{Y|S}\left(y\right|s^{\prime })}=\frac{\mathsf{\Lambda }\left(y\right)}{\mathsf{\Psi }\left(y\right)}\le {\mathrm{e}}^{\epsilon }.$$

(4)

3. Asymmetric Local Information Privacy

According to (3), LIP restricts the decrement of $log\mathsf{\Psi }\left(y\right)$ and increment of $log\mathsf{\Lambda }\left(y\right)$ by the symmetric bounds. However, we demonstrate that these metrics have a distinct range of values and probabilities of appearance in the dataset, $P_{SY}(s,y)$. We plot the histogram of $log\mathsf{\Psi }\left(y\right)$ and $log\mathsf{\Lambda }\left(y\right)$ for ${10}^3$ randomly generated distributions in Figure 1, where $\left|\mathcal{X}\right|=17$ and $\left|\mathcal{S}\right|=5$. In this figure, the range of $log\mathsf{\Psi }\left(y\right)$ is $[-12,-0.06]$, much larger than the range of $log\mathsf{\Lambda }\left(y\right)$, $[0.02,1.64]$. Moreover, the maximum probability of $log\mathsf{\Psi }\left(y\right)$ is much lower than the maximum probability of $log\mathsf{\Lambda }\left(y\right)$. We refer to these properties as lift asymmetry. Since high values of $|log\mathsf{\Psi }(y\left)\right|$ have a significantly lower probability (for example, in Figure 1, the probability of $|log\mathsf{\Psi }(y\left)\right|\ge 6$ is near zero) than the $log\mathsf{\Lambda }\left(y\right)$, we can relax the min-lift privacy by allocating a higher privacy budget to it while applying a stricter bound for the max-lift. Thus, we propose asymmetric local information privacy (ALIP), where we consider different privacy budgets ${\epsilon }_l$ and ${\epsilon }_u$ for $|log\mathsf{\Psi }(y\left)\right|$ and $log\mathsf{\Lambda }\left(y\right)$, respectively.

This will result in the following notion of privacy, which is more compatible with the lift asymmetry property.

Definition 3.

For ${\epsilon }_l,{\epsilon }_u\in {\mathbb{R}}_{+}$, a privacy mechanism $\mathcal{M}:\mathcal{X}\to \mathcal{Y}$ is $({\epsilon }_l,{\epsilon }_u)$-asymmetric local information private, or $({\epsilon }_l,{\epsilon }_u)$-ALIP, with respect to S, if for all $y\in \mathcal{Y}$,

$${\mathrm{e}}^{-{\epsilon }_l}\le \mathsf{\Psi }\left(y\right)\mathit{and}\mathsf{\Lambda }\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u}.$$

(5)

The following proposition indicates how $({\epsilon }_l,{\epsilon }_u)$-ALIP restricts average privacy leakage measures and LDP.

Proposition 1.

If $({\epsilon }_l,{\epsilon }_u)$-ALIP is satisfied, then

 1. 

$I(S;Y)\le {\epsilon }_u$;

 2. 

$T(S;Y)\le \frac{1}{2}({\mathrm{e}}^{{\epsilon }_u}-1)$ and ${\chi }^2(S;Y)\le {({\mathrm{e}}^{{\epsilon }_u}-1)}^2$;

 3. 

$I_{\alpha }^S(S;Y)\le \frac{\alpha }{\alpha -1}{\epsilon }_u$ and $I_{\alpha }^A(S;Y)\le \frac{\alpha }{\alpha -1}{\epsilon }_u$;

 4. 

ε-LDP is satisfied where $\epsilon ={\epsilon }_l+{\epsilon }_u$;

where $T(S;Y)$ is the total variation distance, ${\chi }^2(S;Y)$ is ${\chi }^2$-divergence, $I_{\alpha }^S(S;Y)$ is Sibson MI, and $I_{\alpha }^A(S;Y)$ is Arimoto MI.

Proof. 

The proof is given in Appendix B.    □

Proposition 1-1–3 demonstrate that average measures are bounded with the max-lift privacy budget. In Section 3.1, we show that ALIP can enhance utility via relaxing min-lift ${\epsilon }_l>{\epsilon }_u$, where a smaller upper bound is allocated to the max-lift and average measures in Proposition 1. Proposition 1–4 shows the relationship between $({\epsilon }_l,{\epsilon }_u)$-ALIP and $\epsilon$-LDP. We introduce a variable $\lambda \in (0,1)$ to have a convenient representation of this relationship as follows: for an LDP privacy budget $\epsilon$, if we set ${\epsilon }_l=\lambda \epsilon$ and ${\epsilon }_u=(1-\lambda )\epsilon$, we have ${\epsilon }_l+{\epsilon }_u=\epsilon$. Thus, varying $\lambda$ gives rise to different $({\epsilon }_l,{\epsilon }_u)$-ALIP scenarios within the same budget for $\epsilon$-LDP. If $\lambda <0.5$, we have relaxation on the max-lift privacy; if $\lambda >0.5$, it implies relaxation on the min-lift privacy. When $\lambda =0.5$, we have the symmetric case of $\frac{\epsilon }{2}$-LIP, where ${\epsilon }_l={\epsilon }_u=\frac{\epsilon }{2}$.

3.1. ALIP Privacy–Utility Trade-Off

In this subsection, we propose a watchdog mechanism based on ALIP and LDP and an asymmetric ORR (AORR) mechanism for ALIP to perturb data and achieve privacy protection. We observe the PUT of ALIP and LDP, where the utility is measured by MI between X and Y, $I(X;Y)$.

3.1.1. Watchdog Mechanism

Watchdog privacy mechanism bipartitions $\mathcal{X}$ into low-risk and high-risk subsets denoted by ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$, respectively, and only randomises high-risk symbols. In the existing LIP, ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$ are determined by symmetric bounds. We propose to use ALIP to obtain ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$:

$$\begin{array}{c}{\mathcal{X}}_L\triangleq \{x\in \mathcal{X}:{\mathrm{e}}^{-{\epsilon }_l}\le \mathsf{\Psi }\left(x\right)and\mathsf{\Lambda }\left(x\right)\le {\mathrm{e}}^{{\epsilon }_u}\}and{\mathcal{X}}_H=\mathcal{X}\setminus {\mathcal{X}}_L.\end{array}$$

(6)

For LDP, ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$ are given by

$$\begin{array}{c}{\mathcal{X}}_L\triangleq \{x\in \mathcal{X}:\mathsf{\Gamma }\left(x\right)\le {\mathrm{e}}^{\epsilon }\}and{\mathcal{X}}_H=\mathcal{X}\setminus {\mathcal{X}}_L.\end{array}$$

(7)

After obtaining ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$, the privacy mechanism will be

$$\mathcal{M}=\left\{\begin{array}{cc}{\mathbf{1}}_{\{x=y\}},\hfill & x,y\in {\mathcal{X}}_L={\mathcal{Y}}_L,\hfill \\ r\left(y\right|x),\hfill & x\in {\mathcal{X}}_H,y\in {\mathcal{Y}}_H,\hfill \\ 0,\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\hfill \end{array}\right.$$

(8)

where ${\mathbf{1}}_{\{x=y\}}$ indicates the publication of low-risk symbols without alteration, and $r\left(y\right|x)$ is the randomisation on high-risk symbols, where ${\sum }_{y\in {\mathcal{Y}}_H}r\left(y\right|x)=1$.

An instance of $r\left(y\right|x)$ is the X-invariant randomisation, if $r\left(y\right|x)=\mathcal{R}(y)$ for $x\in {\mathcal{X}}_H,y\in {\mathcal{Y}}_H$, and ${\sum }_{y\in {\mathcal{Y}}_H}\mathcal{R}\left(y\right)=1$. An example of $\mathcal{R}\left(y\right)$ is the uniform randomisation $\mathcal{R}\left(y\right)=\frac{1}{|{\mathcal{Y}}_H|}$ with the special case of complete merging, where $|{\mathcal{Y}}_H|=1$, and all $x\in {\mathcal{X}}_H$ are mapped to one super symbol $y^{*}\in {\mathcal{Y}}_H$. It was proved in [25] for LIP that X-invariant randomisation minimises privacy leakage in ${\mathcal{X}}_H$. Accordingly, if we apply ALIP in the watchdog mechanism, for ${\mathcal{X}}_H\ne ⌀$, the minimum leakages over ${\mathcal{X}}_H$ are

$$\begin{array}{c}{\overline{\epsilon }}_u:=\underset{s\in \mathcal{S}}{max}i(s,{\mathcal{X}}_H)=\underset{s\in \mathcal{S}}{max}logl(s,{\mathcal{X}}_H)=\underset{s\in \mathcal{S}}{max}log\frac{P\left({\mathcal{X}}_H\right|s)}{P\left({\mathcal{X}}_H\right)},\end{array}$$

(9)

$$\begin{array}{c}{\overline{\epsilon }}_l:=\left|\underset{s\in \mathcal{S}}{min}i(s,{\mathcal{X}}_H)\right|=\left|\underset{s\in \mathcal{S}}{min}logl(s,{\mathcal{X}}_H)\right|=\left|\underset{s\in \mathcal{S}}{min}log\frac{P\left({\mathcal{X}}_H\right|s)}{P\left({\mathcal{X}}_H\right)}\right|,\end{array}$$

(10)

where ${\displaystyle P\left({\mathcal{X}}_H\right|s)=\sum _{x\in {\mathcal{X}}_H}{P}_{X|S}\left(x\right|s)}$ and ${\displaystyle P\left({\mathcal{X}}_H\right)=\sum _{x\in {\mathcal{X}}_H}{P}_X\left(x\right).}$

X-invariant randomisation is also applicable for LDP, and the following theorem shows that it minimises LDP privacy leakage in ${\mathcal{X}}_H$.

Theorem 1.

In the LDP watchdog mechanism where ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$ are determined according to (7), X-invariant randomisation minimises privacy leakage in ${\mathcal{X}}_H$ measured by $\mathsf{\Gamma }\left(y\right)$ in (4).

Proof. 

The proof is given in Appendix C.    □

In the watchdog mechanism with X-invariant randomisation, the resulting utility measured by MI between X and Y is given by

$$I(X;Y)=H\left(X\right)-\sum _{x\in {\mathcal{X}}_H}{P}_X\left(x\right)log\frac{P\left({\mathcal{X}}_H\right)}{P_X\left(x\right)}.$$

(11)

In [25], it was verified that $I(X;Y)$ in (11) is monotonic in ${\mathcal{X}}_H$: if ${\mathcal{X}}_H^{{}^{\prime }}\subset {\mathcal{X}}_H$ then $I(X;Y)<I^{{}^{\prime }}(X;Y)$, where $I^{{}^{\prime }}(X;Y)$ is the resulting utility of ${\mathcal{X}}_H^{{}^{\prime }}$.

Proposition 2.

In the watchdog mechanism with X-invariant randomisation, for a given LDP privacy budget ε, $\lambda \in (0,1)$, and ALIP privacy budgets ${\epsilon }_l=\lambda \epsilon ,{\epsilon }_u=(1-\lambda )\epsilon$, LDP results in higher utility and than ALIP.

Proof. 

Denote the high-risk subset for LDP by ${\mathcal{X}}_H^{{}^{\prime }}$ and for ALIP by ${\mathcal{X}}_H$. We have

$${\mathcal{X}}_H^{{}^{\prime }}=\{x\in \mathcal{X}:\frac{\mathsf{\Lambda }\left(x\right)}{\mathsf{\Psi }\left(x\right)}>{\mathrm{e}}^{\epsilon }\}\mathrm{and}{\mathcal{X}}_H=\{x\in \mathcal{X}:\mathsf{\Lambda }\left(x\right)>{\mathrm{e}}^{(1-\lambda )\epsilon }or\mathsf{\Psi }\left(x\right)<{\mathrm{e}}^{-\lambda \epsilon }\}.$$

Based on the remark following (11), it is enough to prove that ${\mathcal{X}}_H^{\prime }\subseteq {\mathcal{X}}_H$. If $x\in {\mathcal{X}}_H^{{}^{\prime }}$, for any given $\lambda \in (0,1)$, there are only two possible cases: either $\mathsf{\Lambda }\left(x\right)>{\mathrm{e}}^{(1-\lambda )\epsilon }$ or $\mathsf{\Lambda }\left(x\right)\le {\mathrm{e}}^{(1-\lambda )\epsilon }$. If $\mathsf{\Lambda }\left(x\right)>{\mathrm{e}}^{(1-\lambda )\epsilon }$, then $x\in {\mathcal{X}}_H$, and our claim is true. If $\mathsf{\Lambda }\left(x\right)\le {\mathrm{e}}^{(1-\lambda )\epsilon }$, we have $x\in {\mathcal{X}}_H^{\prime }\Rightarrow \frac{\mathsf{\Lambda }\left(x\right)}{\mathsf{\Psi }\left(x\right)}>{\mathrm{e}}^{\epsilon }\Rightarrow \mathsf{\Psi }\left(x\right)<\mathsf{\Lambda }\left(x\right){\mathrm{e}}^{-\epsilon }$. We assumed that $\mathsf{\Lambda }\left(x\right)\le {\mathrm{e}}^{(1-\lambda )\epsilon }$; therefore, $\mathsf{\Psi }\left(x\right)<\mathsf{\Lambda }\left(x\right){\mathrm{e}}^{-\epsilon }\le {\mathrm{e}}^{(1-\lambda )\epsilon }{\mathrm{e}}^{-\epsilon }={\mathrm{e}}^{-\lambda \epsilon }$. Since $\mathsf{\Psi }\left(x\right)<{\mathrm{e}}^{-\lambda \epsilon }$, we have $x\in {\mathcal{X}}_H$.  □

This proposition shows the result of applying LDP and ALIP in the watchdog mechanism in terms of the privacy–utility trade-off. While both $\epsilon$-LDP and $(\lambda \epsilon ,(1-\lambda \left)\epsilon \right)$-ALIP imply the same LDP privacy budget, LDP results in fewer high-risk symbols compared to ALIP. This needs to be considered when one applies the watchdog mechanism to achieve LDP or ALIP privacy. Although having fewer high-risk symbols provides better utility, it may compromise privacy. In other words, when ${\mathcal{X}}_H^{\prime }\subseteq {\mathcal{X}}_H$, then the privacy leakage of the partition $\{{\mathcal{X}}_L^{\prime },{\mathcal{X}}_H^{\prime }\}$ is greater than or equal to the privacy leakage of the partition $\{{\mathcal{X}}_L,{\mathcal{X}}_H\}$. As a result, it is possible that $\epsilon$-LDP cannot achieve the desired $(\lambda \epsilon ,(1-\lambda \left)\epsilon \right)$-ALIP privacy level for a given $\lambda$.

Watchdog mechanism with X-invariant randomisation is a powerful method with low complexity that can be easily applied to instance-wise measures. However, it significantly degrades the utility [25] because X-invariant randomisation obfuscates all high-risk symbols together to minimise privacy leakage, with the cost of deteriorating data resolution. In Section 4, we propose subset merging randomisation to enhance the utility of the watchdog mechanism.

3.1.2. Asymmetric Optimal Random Response (AORR)

ORR was proposed in [28] as a localised instance-wise replacement of the privacy funnel [12]. It is the solution to the optimal utility problem subject to $\epsilon$-LIP or $\epsilon$-LDP constraints. For ALIP, we propose asymmetric optimal random response (AORR), which is defined as

$$\begin{array}{cc}\hfill & \underset{\begin{array}{c}{P}_{X|Y},P_Y\end{array}}{max}I(X;Y)\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& S-X-Y\hfill \\ \hfill & {\mathrm{e}}^{-{\epsilon }_l}\le \mathsf{\Psi }\left(y\right)\mathrm{and}\mathsf{\Lambda }\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u},\forall y\in \mathcal{Y}.\hfill \end{array}$$

(12)

Privacy constraints in this optimisation problem form a closed, bounded, convex polytope [28]. It has been proved that vertices of this polytope are the feasible candidates that maximise MI and satisfy privacy constraints [7,28,37]. However, the number of vertices grows exponentially in the dimension of the polyhedron, which is $\left|\mathcal{X}\right|\left(\right|\mathcal{X}|-1)$ for LDP and $\left(\left|\mathcal{X}\right|-1\right)$ for LIP. This makes ORR computationally cumbersome for large $\left|\mathcal{X}\right|$. Accordingly, [28] suggests some approaches with lower complexity than ORR to avoid vertex enumeration for the larger sizes of $\mathcal{X}$, but this comes at the cost of lower utility.

3.1.3. Numerical Results

Here, we demonstrate the privacy leakage and utility of AORR and the watchdog mechanism under ALIP. For the utility, we use normalised MI (NMI)

$$\mathrm{NMI}=\frac{I(X;Y)}{H\left(X\right)}\in [0,1].$$

It is clear that the maximum possible utility is obtained when X is published without randomisation, where $Y=X$ and $I(X;Y)=H\left(X\right)$. Thus, $I(X;Y)\le H\left(X\right)$ and NMI $\le 1$.

We present numerical results for both synthetic and real datasets using MATLAB. For synthetic data, we randomly generated ${10}^3$ distributions for the watchdog mechanism and 100 distributions for the AORR where $\left|\mathcal{X}\right|=17$ and $\left|\mathcal{S}\right|=5$. These distributions were generated by normalising the output of the rand function in MATLAB. For real datasets, we used the Adult dataset [38] and set $S=\left\{\mathrm{relationship}\right\}$ and $X=\left\{\mathrm{Occupation}\right\}$, where $\left|\mathcal{S}\right|=5$ and $\left|\mathcal{X}\right|=15$. In all scenarios, $\epsilon$ varies from $0.25$ to 8, and we consider three cases for $({\epsilon }_u,{\epsilon }_l)$-ALIP, where $\lambda \in \{0.35,0.5,0.65\}$, ${\epsilon }_l=\lambda \epsilon$, and ${\epsilon }_u=(1-\lambda )\epsilon$. The results of the watchdog mechanism are shown in Figure 2 and Figure 3 for synthetic and real data, respectively; while the AORR results are presented in Figure 4 and Figure 5. The figures display NMI, $log\left({max}_y\mathsf{\Lambda }\left(y\right)\right)$ (max-lift leakage), and $\left|log\left({min}_y\mathsf{\Psi }\left(y\right)\right)\right|$ (min-lift leakage) versus the LDP privacy budget $\epsilon$ for real data, and the mean values of the same quantities are shown for synthetic data.

In Figure 2a and Figure 3a, we observe that in the watchdog mechanism, LDP provides higher utility and leakage than ALIP for all values of $\epsilon$ and $\lambda$, which confirms Proposition 2. Figure 2a, Figure 3a, Figure 4a and Figure 5a demonstrate that the min-lift relaxation, $\lambda =0.65$, enhances utility in the watchdog and AORR mechanisms for $\epsilon >1$. Note that in all figures, $\lambda =0.5$ refers to $\frac{\epsilon }{2}$-LIP. On the other hand, $\lambda =0.35$ results in lower utility. Generally, any value of $\lambda <0.5$ reduces utility since it strictly bounds the min-lift while relaxing the max-lift. As the min-lift has a wider range of values, achieving this strict bound enlarges the set ${\mathcal{X}}_H$ and requires randomising more symbols, which reduces utility. Another observation here is that AORR incurs significantly higher utility than the watchdog mechanism. For instance, when $\lambda =0.5$ and $\epsilon =2$, the watchdog mechanism results in a utility of $0.52$ for synthetic data and $0.73$ for the real data, while AORR has a utility of $0.94$ and $0.96$ for the synthetic and real data, respectively. AORR finds the optimal utility, which, due to PUT, necessarily results in the highest leakage subject to privacy constraints. However, the watchdog mechanism is a nonoptimal solution that minimises leakage of high-risk symbols to provide strong privacy protection, which deteriorates utility. To solve this drawback of the watchdog mechanism, we propose a subset randomisation method in the following section.

4. Subset Merging in Watchdog Mechanism

The watchdog mechanism with X-invariant randomisation is a low-complexity method that can be easily applied when the privacy measures are symbol-wise. X-invariant randomisation is the optimal privacy protection for the high-risk symbols that minimises privacy leakage in ${\mathcal{X}}_H$ and necessarily results in the worst data resolution. Thus, in this section, we propose the subset merging algorithm to improve data resolution by randomising disjoint subsets of high-risk symbols and enhancing utility in the watchdog mechanism. In the following, we show that applying X-invariant randomisation to disjoint subsets of ${\mathcal{X}}_H$ increases the utility.

Let ${\mathcal{G}}_{{\mathcal{X}}_H}=\{{\mathcal{X}}_1,{\mathcal{X}}_2,\cdots {\mathcal{X}}_g\}$ be a partition of ${\mathcal{X}}_H$, where for every $i\in \left[g\right]$, ${\mathcal{X}}_i\subseteq {\mathcal{X}}_H$: ${\mathcal{X}}_i\cap {\mathcal{X}}_j=⌀,i\ne j$, and ${\displaystyle {\mathcal{X}}_H={\cup }_{i=1}^g{\mathcal{X}}_i}$. We randomise each subset ${\mathcal{X}}_i\in {\mathcal{G}}_{{\mathcal{X}}_H}$ by X-invariant randomisation ${\mathcal{R}}_{{\mathcal{Y}}_i}\left(y\right)$ for $x\in {\mathcal{X}}_i$ and $y\in {\mathcal{Y}}_i$, where ${\sum }_{y\in {\mathcal{Y}}_i}{\mathcal{R}}_{{\mathcal{Y}}_i}\left(y\right)=1$. The resulting MI between X and Y is

$$I(X;Y)=H\left(X\right)-\sum _{i=1}^g\sum _{x\in {\mathcal{X}}_i}{P}_X\left(x\right)log\frac{P\left({\mathcal{X}}_i\right)}{P_X\left(x\right)}.$$

(13)

Definition 4.

Assume two partitions, ${\mathcal{G}}_{{\mathcal{X}}_H}=\{{\mathcal{X}}_1,\cdots ,{\mathcal{X}}_g\}$ and ${\mathcal{G}}_{{\mathcal{X}}_H}^{{}^{\prime }}=\{{\mathcal{X}}_1^{{}^{\prime }},\cdots ,{\mathcal{X}}_{g^{\prime }}^{{}^{\prime }}\}$. We say that ${\mathcal{G}}_{{\mathcal{X}}_H}^{{}^{\prime }}$ is a refinement of ${\mathcal{G}}_{{\mathcal{X}}_H}$, or ${\mathcal{G}}_{{\mathcal{X}}_H}$ is an aggregation of ${\mathcal{G}}_{{\mathcal{X}}_H}^{{}^{\prime }}$, if for every $i\in \left[g\right]$, ${\mathcal{X}}_i={\cup }_{j\in J_i}{\mathcal{X}}_j^{{}^{\prime }}$ where $J_i\subseteq \left[g^{\prime }\right]$, and $P\left({\mathcal{X}}_i\right)={\sum }_{j\in J_i}P\left({\mathcal{X}}_j^{{}^{\prime }}\right)$ (this definition is inspired from [39] (Definition 10)).

If ${\mathcal{G}}_{{\mathcal{X}}_H}^{{}^{\prime }}$ is a refinement of ${\mathcal{G}}_{{\mathcal{X}}_H}$, then $I_{{\mathcal{G}}_{{\mathcal{X}}_H}}(X;Y)\le I_{{\mathcal{G}}_{{\mathcal{X}}_H}^{{}^{\prime }}}(X;Y)$.

Obtaining the optimal ${\mathcal{G}}_{{\mathcal{X}}_H}$ that maximises utility and satisfies privacy constraints is a combinatorial optimisation problem over all possible partitions of ${\mathcal{X}}_H$, which is cumbersome to solve. Therefore, we propose a heuristic method in the following.

4.1. Greedy Algorithm to Make Refined Subsets of High-Risk Symbols

In Algorithm 1, we propose a bottom-up algorithm that constitutes a partition of ${\mathcal{X}}_H$ by merging high-risk symbols in disjoint subsets. It works based on a leakage risk metric for each $x\in {\mathcal{X}}_H$: $\omega \left(x\right)=\mathsf{\Lambda }\left(x\right)+\mathsf{\Psi }\left(x\right)$ for ALIP and $\omega \left(x\right)=\mathsf{\Gamma }\left(x\right)$ for LDP. For LIP, $\omega \left(x\right)=max\{log\mathsf{\Lambda }(x),|log\mathsf{\Psi }\left(x\right)\left|\right\}$. This metric is used to order the subsets by the privacy risk level. Accordingly, to constitute a subset ${\mathcal{X}}_i\subseteq {\mathcal{X}}_H$, Algorithm 1 bootstraps from the highest risk symbol ${\mathcal{X}}_i=\{arg{max}_{x\in {\mathcal{X}}_H}\omega \left(x\right)\}$ (line 5). Then, it merges a symbol $x^{*}$ with ${\mathcal{X}}_i$ that minimises $\omega ({\mathcal{X}}_i\cup x^{*})$ (line 7), as long as the privacy constraints are satisfied in ${\mathcal{X}}_i$ (line 6). The ALIP privacy constraints for a subset ${\mathcal{X}}_i$ are given by

$${\mathrm{e}}^{-{\epsilon }_l}\le \mathsf{\Psi }\left({\mathcal{X}}_i\right)and\mathsf{\Lambda }\left({\mathcal{X}}_i\right)\le {\mathrm{e}}^{{\epsilon }_u},$$

(14)

where $\mathsf{\Psi }\left({\mathcal{X}}_i\right)={min}_{s\in \mathcal{S}}\frac{{\sum }_{x\in {\mathcal{X}}_i}{P}_{X|S}\left(x\right|s)}{{\sum }_{x\in {\mathcal{X}}_i}{P}_X\left(x\right)}$ and $\mathsf{\Lambda }\left({\mathcal{X}}_i\right)={max}_{s\in \mathcal{S}}\frac{{\sum }_{x\in {\mathcal{X}}_i}{P}_{X|S}\left(x\right|s)}{{\sum }_{x\in {\mathcal{X}}_i}{P}_X\left(x\right)}$. For LDP constraint, we have $\mathsf{\Gamma }\left({\mathcal{X}}_i\right)=\frac{\mathsf{\Lambda }\left({\mathcal{X}}_i\right)}{\mathsf{\Psi }\left({\mathcal{X}}_i\right)}\le {\mathrm{e}}^{\epsilon }$. In Algorithm 1, we used ALIP privacy constraints for the while loops condition in lines 4, 6, and 12. For LDP, the privacy constraint is changed to $\mathsf{\Gamma }\left({\mathcal{X}}_Q\right)>\epsilon$, and $\omega \left(x\right)$ for LDP is applied. After the constitution of the partition ${\mathcal{G}}_{{\mathcal{X}}_H}$, the last subset ${\mathcal{X}}_g$ may not meet privacy constraints. Therefore, the leakage of ${\mathcal{X}}_g$ is checked (line 12), and if there is a privacy breach, an agglomerate ${\mathcal{X}}_g$ is made by merging other subsets to it that minimises subset risk, $\omega \left({\mathcal{X}}_g\right)=\mathsf{\Lambda }\left({\mathcal{X}}_g\right)+\mathsf{\Psi }\left({\mathcal{X}}_g\right)$ (lines 13–14), until privacy constraints are satisfied.

Algorithm 1: Subset merging in the watchdog mechanism.

4.2. Numerical Results

We show PUT for ALIP and LDP under subset merging randomisation in Figure 6 and Figure 7 for synthetic and real data, respectively, with the same setup for the watchdog mechanism in Section 3.1.3. Compared with the complete merging (Figure 2 and Figure 3), the utility was enhanced significantly for both LDP and ALIP in all scenarios under the same privacy constraint. For instance, consider the symmetric case $\lambda =0.5$ when $\epsilon =1$, and compare PUT between the subset and complete merging. Figure 6a and Figure 7a demonstrate a utility value of around $0.73$ for the subset merging compared to the utilities of $0.17$ and $0.28$ for the complete merging in Figure 2a and Figure 3a, which are almost $320\%$ and $160\%$ utility enhancement. Moreover, as Figure 6b,c and Figure 7b,c illustrate, privacy constraints are satisfied in all cases.

5. Subset Random Response

In the previous section, we showed that subset merging enhances utility in the watchdog mechanism significantly. In this section, we propose a method to decrease the complexity of AORR for large datasets. We adopt AORR for subsets of ${\mathcal{X}}_H$ to decrease the complexity of AORR for large sets such that random response becomes applicable for typically an order of magnitude larger $\mathcal{X}$.

The AORR optimisation problem in (12) is equivalent to the following problem:

$$\begin{array}{cc}\hfill & H\left(x\right)-\underset{P_{X|Y},P_Y}{min}H\left(X\right|Y)\hfill \\ \hfill & \mathrm{s}.\mathrm{t}.S-X-Y\hfill \\ \hfill & {\mathrm{e}}^{-{\epsilon }_l}\le \mathsf{\Psi }\left(y\right)\mathrm{and}\mathsf{\Lambda }\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u},\forall y\in \mathcal{Y}.\hfill \end{array}$$

(15)

To reduce the complexity of (15), we divide $\mathcal{X}$ into ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$, similar to the watchdog mechanism, and make a partition ${\mathcal{G}}_{{\mathcal{X}}_H}=\{{\mathcal{X}}_1,{\mathcal{X}}_2,\cdots {\mathcal{X}}_g\}$ from ${\mathcal{X}}_H$. We randomise each subset ${\mathcal{X}}_i\in {\mathcal{G}}_{{\mathcal{X}}_H}$, $i\in \left[g\right]$, separately by a randomisation pair $\left({\mathbf{Q}}_i,{\mathbf{q}}_i\right)$, where ${\mathbf{Q}}_i$ is a matrix in ${\mathbb{R}}^{|{\mathcal{X}}_i|\times |{\mathcal{Y}}_i|}$ and ${\mathbf{q}}_i$ is a vector in ${\mathbb{R}}^{|{\mathcal{Y}}_i|}$.

The elements of ${\mathbf{Q}}_i$ and ${\mathbf{q}}_i$ are given by

$$\begin{array}{c}{\mathbf{Q}}_i\left(x\right|y)=Pr[X=x|Y=y],x\in {\mathcal{X}}_i,y\in {\mathcal{Y}}_i,\end{array}$$

(16)

$$\begin{array}{c}{\mathbf{q}}_i\left(y\right)=Pr[Y=y],y\in {\mathcal{Y}}_i.\end{array}$$

(17)

For each $y\in {\mathcal{Y}}_i$, we have ${\sum }_{x\in {\mathcal{X}}_i}{\mathbf{Q}}_i\left(x\right|y)=1$. Consequently, $H\left(X\right|Y)={\sum }_{i\in \left[g\right]}{H}_i\left(X\right|Y)$, where

$$H_i\left(X\right|Y)=-\sum _{y\in {\mathcal{Y}}_i}{\mathbf{q}}_i\left(y\right)\sum _{x\in {\mathcal{X}}_i}{\mathbf{Q}}_i\left(x\right|y)log{\mathbf{Q}}_i\left(x\right|y),i\in \left[g\right].$$

(18)

This setting turns (15) into g optimisation problems for each subset ${\mathcal{X}}_i\in {\mathcal{G}}_{{\mathcal{X}}_H},$$i\in \left[g\right]$ as follows:

$$\begin{array}{cc}\hfill & \underset{{\mathbf{Q}}_i,{\mathbf{q}}_i}{min}{H}_i\left(X\right|Y)\hfill \end{array}$$

(19)

$$\begin{array}{cccc}\hfill \mathrm{s}.\mathrm{t}.& 0\le {\mathbf{q}}_i\left(y\right),\hfill & \hfill & \forall y\in {\mathcal{Y}}_i,\hfill \end{array}$$

(20)

$$\begin{array}{cccc}\hfill & 0\le {\mathbf{Q}}_i\left(x\right|y),\hfill & \hfill & \forall x\in {\mathcal{X}}_i,\forall y\in {\mathcal{Y}}_i,\hfill \end{array}$$

(21)

$$\begin{array}{cccc}\hfill & \sum _{x\in {\mathcal{X}}_i}{\mathbf{Q}}_i\left(x\right|y)=1,\hfill & \hfill & \forall y\in {\mathcal{Y}}_i,\hfill \end{array}$$

(22)

$$\begin{array}{cccc}\hfill & \sum _{y\in {\mathcal{Y}}_i}{\mathbf{Q}}_i\left(x\right|y){\mathbf{q}}_i\left(y\right)=P_X\left(x\right),\hfill & \hfill & x\in {\mathcal{X}}_i,\hfill \end{array}$$

(23)

$$\begin{array}{cccc}\hfill & {\mathrm{e}}^{-{\epsilon }_l}{P}_S\left(s\right)\le \sum _{x\in {\mathcal{X}}_i}{P}_{S|X}\left(s\right|x){\mathbf{Q}}_i\left(x\right|y)\le {\mathrm{e}}^{{\epsilon }_u}{P}_S\left(s\right),\hfill & \hfill & \forall s\in \mathcal{S},y\in {\mathcal{Y}}_i.\hfill \end{array}$$

(24)

The columns of the randomisation matrix ${\mathbf{Q}}_i$, $i\in \left[g\right]$ can be expressed as the members of a convex and bounded polytope ${\Pi }_i$, which is given by the following constraints:

$${\mathsf{\Pi }}_i=\left\{\begin{array}{cc}\hfill & \mathbf{v}\in {\mathbb{R}}^{|{\mathcal{X}}_i|}:\hfill \\ \hfill & 0\le v_k,\forall k\in \left[\right|{\mathcal{X}}_i\left|\right],\hfill \\ \hfill & \sum _{k=1}^{|{\mathcal{X}}_i|}{v}_k=1,\hfill \\ \hfill & {\mathrm{e}}^{-{\epsilon }_l}{P}_S\left(s\right)\le \sum _{x\in {\mathcal{X}}_i}{P}_{S|X}\left(s\right|x)v_k\le {\mathrm{e}}^{{\epsilon }_u}{P}_S\left(s\right),\forall s\in \mathcal{S},k\in \left[\right|{\mathcal{X}}_i\left|\right]\hfill \end{array}\right\}.$$

(25)

For each ${\mathcal{X}}_i\in {\mathcal{G}}_{{\mathcal{X}}_H},$ $i\in \left[g\right]$, let ${\mathcal{V}}_i=\{{\mathbf{v}}_1^i\cdots ,{\mathbf{v}}_M^i\}$ be the vertices of ${\mathsf{\Pi }}_i$ in (25), $\mathrm{H}\left({\mathbf{v}}_k^i\right)$ be the entropy of each ${\mathbf{v}}_k^i$ for $k\in \left[M\right]$, ${\mathbf{P}}_{\mathbf{X}}^{\mathbf{i}}$ be the probability vector of $x\in {\mathcal{X}}_i$, and ${\beta }^i$ be the solution to the following optimisation:

$$\begin{array}{cc}\hfill & \underset{{\beta }^i\in {\mathbb{R}}^M}{min}\sum _{k=1}^M\mathrm{H}\left({\mathbf{v}}_k^i\right){\beta }_k^i,\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& {\beta }_k^i\ge 0,\forall k\in \left[M\right],\hfill \\ \hfill & \sum _{k=1}^M{\mathbf{v}}_k^i{\beta }_k^i={\mathbf{P}}_{\mathbf{X}}^{\mathbf{i}}.\hfill \end{array}$$

(26)

Then, ${\mathcal{Y}}_i$ and $\left({\mathbf{Q}}_i,{\mathbf{q}}_i\right)$ are given by

$$\begin{array}{c}{\mathcal{Y}}_i=\{y:{\beta }_y^i\ne 0\};\end{array}$$

(27)

$$\begin{array}{c}{\mathbf{q}}_i\left(y\right)={\beta }_y^i\mathrm{and}{\mathbf{Q}}_i(.|y)={\mathbf{v}}_y^i,y\in {\mathcal{Y}}_i.\end{array}$$

(28)

The $({\epsilon }_l,{\epsilon }_u)$-ALIP protocol, $\mathcal{M}:\mathcal{X}\to \mathcal{Y}$, is given by the pair of $(P_{X|Y},P_Y)$ as follows:

$$P_{X|Y}=\left\{\begin{array}{cc}{\mathbf{1}}_{\{x=y\}},\hfill & x,y\in {\mathcal{X}}_L={\mathcal{Y}}_L,\hfill \\ {\mathbf{Q}}_i\left(x\right|y),\hfill & x\in {\mathcal{X}}_i,y\in {\mathcal{Y}}_i,i\in \left[g\right],\hfill \\ 0,\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e};\hfill \end{array}\right.$$

(29)

$$P_Y=\left\{\begin{array}{cc}{P}_X\left(y\right),\hfill & y\in {\mathcal{Y}}_L,\hfill \\ {\mathbf{q}}_i\left(y\right),\hfill & y\in {\mathcal{Y}}_i,i\in \left[g\right].\hfill \end{array}\right.$$

(30)

5.1. Algorithm for Subset Random Response

We propose Algorithm 2 to implement AORR for subsets of ${\mathcal{X}}_H$, which we call subset random response (SRR). In this algorithm, first, we obtain a partition ${\mathcal{G}}_{{\mathcal{X}}_H}=\{{\mathcal{X}}_1,{\mathcal{X}}_2,\cdots {\mathcal{X}}_g\}$ of ${\mathcal{X}}_H$ via Algorithm 1. Then, based on ${\mathcal{G}}_{{\mathcal{X}}_H}$, we make another partition ${\mathcal{O}}_{{\mathcal{X}}_H}$ and find the optimal random response for each subset ${\mathcal{X}}_i^{{}^{\prime }}\in {\mathcal{O}}_{{\mathcal{X}}_H}$ (line 5). By obtaining the optimal random responses for all subsets, we obtain a pair $({\mathbf{Q}}_i,{\mathbf{q}}_i)$ for each subset ${\mathcal{X}}_i^{{}^{\prime }}$, and consequently $P_{X|Y}$ and $P_Y$, by (29) and (30) (lines 20–23). The while loop in lines 7–14 is for the particular cases when the polytope in (25) is empty for a subset ${\mathcal{X}}_i^{\prime }$. It may occur for strict privacy conditions where the privacy budget is very small. Since we reduce the dimension of the original polytope in (15), it increases the possibility that no feasible random response exists in some cases. Therefore, in such cases, we make a union with other subsets until we have a nonempty polytope. If $|{\mathcal{G}}_{{\mathcal{X}}_H}|>0$, then we make a union with another subset in ${\mathcal{G}}_{{\mathcal{X}}_H}$ (line 9). If $|{\mathcal{G}}_{{\mathcal{X}}_H}|=0$, it means that ${\mathcal{X}}_{g^{\prime }}^{\prime }$ is the last subset in ${\mathcal{O}}_{{\mathcal{X}}_H}$; therefore, we make a union with previously made subsets in ${\mathcal{O}}_{{\mathcal{X}}_H}$ and update the index $g^{\prime }$ (line 12). Then, if the condition in lines 17–18 is for the cases where there is no feasible polytope after making a union of all subsets, this means that the problem in (15) cannot be solved. Whenever this occurs, we apply the subset merging mechanism.

The number of polytope vertices in AORR is $n\sim O\left(exp\left(\right|\mathcal{X}|-1)\right)$, and the time complexity is $O\left(n\right)$. As $\left|\mathcal{X}\right|$ increases, the complexity of AORR increases exponentially in the $\left|\mathcal{X}\right|-1$. In SRR, for each ${\mathcal{X}}_i\in {\mathcal{G}}_{{\mathcal{X}}_H}$, $i\in \left[g\right]$, the number of vertices is $n_i\sim O(exp\left(\right|{\mathcal{X}}_i|-1))$, and the complexity of SRR is $O\left({max}_i{n}_i\right)$.

Algorithm 2: Subset random response.

5.2. Numerical Results

Here, we compare the PUT of AORR with SRR in Algorithm 2 and subset merging in Algorithm 1. Figure 8 depicts mean values of utility, leakage, and time complexity for 100 randomly generated distributions where $\lambda =0.65$ and simulation setup is the same as that in Section 3.1.3. The result of the Adult dataset is also shown in Figure 9.

Figure 8a–c and Figure 9 demonstrate that SRR results in better utility and higher leakage than subset merging, and its PUT is very close to AORR. Figure 8d illustrates the processing time of each mechanism for synthetic data from which we observe that the complexity of AORR and SRR is much higher than the subset merging. Running SRR is less complex than AORR for strict privacy constraints ($\epsilon <1$) and for $\epsilon >2.5$. While SRR shows higher complexity for some privacy budgets, $1\le \epsilon \le 2.5$, it has the advantage in high-dimension systems. Figure 10 shows a PUT comparison between SRR and subset merging for synthetic data where $\left|\mathcal{X}\right|=200$, $\left|\mathcal{S}\right|=15$, $\epsilon \in \{1,1.25,\cdots ,8\}$, and $\lambda =0.5$. This experiment shows that both SRR and subset merging are applicable to large datasets. Obviously, SRR provides better utility (Figure 10a) and higher leakage (Figure 10b,c), which is still below the given budgets ${\epsilon }_l$ and ${\epsilon }_u$.

6. Lift-Based and Lift-Inverse Measures

In this section, we consider some recently proposed privacy measures that quantify the divergence between the posterior and prior belief on sensitive features, including ${\ell }_1$-norm [32], strong ${\chi }^2$-privacy criterion [33], and $\alpha$-lift [34]. They have been proposed as a stronger version of their corresponding average measures, which are the total variation distance [35], ${\chi }^2$-divergence [40], and Sibson MI [16], respectively. We call them lift-based measures and define them in the following.

Definition 5.

For each $y\in \mathcal{Y}$, lift-based privacy measures are defined as follows:

• The ${\ell }_1$-lift is given by

  $${\mathsf{\Lambda }}_{{\ell }_1}\left(y\right)\triangleq \sum _{s\in \mathcal{S}}{P}_S\left(s\right)|l(s,y)-1|,$$

  (31)

  then the total variation distance will be

  $$T(S;Y)=\frac{1}{2}{\mathbb{E}}_Y\left[{\mathsf{\Lambda }}_{{\ell }_1}\left(Y\right)\right].$$
• The ${\chi }^2$-lift is given by

  $${\mathsf{\Lambda }}_{{\chi }^2}\left(y\right)\triangleq \sum _{s\in \mathcal{S}}{P}_S\left(s\right){\left(l(s,y)-1\right)}^2,$$

  (32)

  then ${\chi }^2$-divergence will be

  $${\chi }^2(S;Y)={\mathbb{E}}_Y\left[{\mathsf{\Lambda }}_{{\chi }^2}\left(Y\right)\right].$$
• The α-lift is given by

  $${\mathsf{\Lambda }}_{\alpha }^S\left(y\right)\triangleq {\left(\sum _{s\in \mathcal{S}}{P}_S\left(s\right)l{(s,y)}^{\alpha }\right)}^{1/\alpha },$$

  (33)

  then Sibson MI will be

  $$I_{\alpha }^S(S;Y)=\frac{\alpha }{\alpha -1}log{\mathbb{E}}_Y\left[{\mathsf{\Lambda }}_{\alpha }^S\left(Y\right)\right].$$

Here, we reveal their relationship with ALIP.

Proposition 3.

If $({\epsilon }_l,{\epsilon }_u)$-ALIP is satisfied, then

 1. 

${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Lambda }}_{{\ell }_1}\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u}-1}$;

 2. 

${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Lambda }}_{{\chi }^2}\left(y\right)\le {({\mathrm{e}}^{{\epsilon }_u}-1)}^2}$;

 3. 

${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Lambda }}_{\alpha }^S\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u}}$.

The proof is given in Appendix D.

Proposition 4.

Let ${\displaystyle s_y=arg\underset{s\in \mathcal{S}}{max}\left[l(s,y)\right]}$ and $\overline{y}=arg{max}_{y\in \mathcal{Y}}\mathsf{\Lambda }\left(y\right)$, then

 1. 

If ${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Lambda }}_{{\ell }_1}\left(y\right)\le \epsilon \Rightarrow \underset{y\in \mathcal{Y}}{max}\mathsf{\Lambda }\left(y\right)\le \epsilon /P_S\left(s_{\overline{y}}\right)+1}$;

 2. 

If ${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Lambda }}_{{\chi }^2}\left(y\right)\le \epsilon \Rightarrow \underset{y\in \mathcal{Y}}{max}\mathsf{\Lambda }\left(y\right)\le \sqrt{\epsilon /P_S\left(s_{\overline{y}}\right)}+1}$;

 3. 

If ${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Lambda }}_{\alpha }^S\left(y\right)\le \epsilon \Rightarrow \underset{y\in \mathcal{Y}}{max}\mathsf{\Lambda }\left(y\right)\le \epsilon /P_S{\left(s_{\overline{y}}\right)}^{\frac{1}{\alpha }}}$.

Proof. 

The proof is given in Appendix E. □

Proposition 3 shows that lift-based measures, similar to their corresponding average leakages, are upper-bounded by the max-lift bound. Proposition 4 indicates that if we bound lift-based measures, they can only restrict the max-lift leakage. Accordingly, if one only applies a lift-based measure to protect privacy, such as in previous works [32,33,34], it may cause significant leakage on the min-lift. Therefore, in the following, we propose lift-inverse measures to bound the min-lift leakage.

6.1. Lift-Inverse Measures

In Propositions 3 and 4, we showed that lift-based measures only bound the max-lift. In this subsection, we present lift-inverse measures to restrict the min-lift leakage, ${min}_{y\in \mathcal{Y}}\mathsf{\Psi }\left(y\right)={min}_{y\in \mathcal{Y}}[{min}_{s\in \mathcal{S}}l(s,y)$].

Definition 6.

For lift-based measures in (31) to (33), we replace $l(s,y)$ with $\frac{1}{l(s,y)}$ and call the resulting quantities lift-inverse measures.

• The ${\ell }_1$-lift-inverse is given by

  $${\mathsf{\Psi }}_{{\ell }_1}\left(y\right)=\sum _{s\in \mathcal{S}}{P}_S\left(s\right)\left|\frac{1}{\ell (s,y)}-1\right|.$$

  (34)
• The ${\chi }^2$-lift-inverse is given by

  $${\mathsf{\Psi }}_{{\chi }^2}\left(y\right)\triangleq \sum _{s\in \mathcal{S}}{P}_S\left(s\right){\left(\frac{1}{\ell (s,y)}-1\right)}^2.$$

  (35)
• The α-lift-inverse is given by

  $${\mathsf{\Psi }}_{\alpha }^S\left(y\right)\triangleq {\left(\sum _{s\in \mathcal{S}}{P}_S\left(s\right){\left(\frac{1}{\ell (s,y)}\right)}^{\alpha }\right)}^{1/\alpha }.$$

  (36)

In the following propositions, we show the relationship between $({\epsilon }_l,{\epsilon }_u)$-ALIP.

Proposition 5.

If $({\epsilon }_l,{\epsilon }_u)$-ALIP is achieved, we have

 1. 

${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Psi }}_{{\ell }_1}\left(y\right)\le {\mathrm{e}}^{{\epsilon }_l}-1;}$

 2. 

${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Psi }}_{{\chi }^2}\left(y\right)\le {\left({\mathrm{e}}^{{\epsilon }_l}-1\right)}^2;}$

 3. 

${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Psi }}_{\alpha }^S\left(y\right)\le {\mathrm{e}}^{{\epsilon }_l}.}$

Proof. 

The proof is provided in Appendix F. □

Proposition 6.

Let ${\displaystyle s_y=arg\underset{s}{min}l(s,y)}$ and ${\displaystyle \underline{y}=arg\underset{y}{min}\left[\mathsf{\Psi }\left(y\right)\right]}$, then

 1. 

If ${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Psi }}_{{\ell }_1}\left(y\right)\le \epsilon \Rightarrow \underset{y\in \mathcal{Y}}{min}\mathsf{\Psi }\left(y\right)\ge \frac{P_S\left(s_{\underline{y}}\right)}{\epsilon +P_S\left(s_{\underline{y}}\right)};}$

 2. 

If ${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Psi }}_{{\chi }^2}\left(y\right)\le \epsilon \Rightarrow \underset{y\in \mathcal{Y}}{min}\mathsf{\Psi }\left(y\right)\ge \frac{\sqrt{P_S\left(s_{\underline{y}}\right)}}{\sqrt{\epsilon }+\sqrt{P_S\left(s_{\underline{y}}\right)}};}$

 3. 

If ${\displaystyle \underset{y\in \mathcal{Y}}{max}{\mathsf{\Psi }}_{\alpha }^S\left(y\right)\le \epsilon \Rightarrow \underset{y\in \mathcal{Y}}{min}\mathsf{\Psi }\left(y\right)\ge {\epsilon }^{-1}{P}_S{\left(s_{\underline{y}}\right)}^{\frac{1}{\alpha }}.}$

Proof. 

The proof is provided in Appendix G. □

Propositions 5 and 6 demonstrate that the aforementioned lift-inverse measures are associated with the min-lift, and bounding them can restrict the min-lift leakage. Since lift-based and lift-inverse measures quantify privacy leakage by a function of lift averaged over sensitive features, they can be regarded as more relaxed measures than the min- and max-lifts.

6.2. PUT and Numerical Results

Optimal randomisations for ${\ell }_1$-lift and ${\chi }^2$-lift privacy, which maximise MI as the utility measure, were proposed in [32,33], respectively. Note that ORR is not applicable to these measures since their privacy constraints are not convex. However, here, we apply the watchdog mechanism with subset merging randomisation to investigate the PUT for lift-based and lift-inverse measures. This application shows that the watchdog mechanism with X-invariant randomisation is a low-complexity method that can be applied to all the aforementioned measures. Moreover, our subset merging algorithm significantly enhances the utility, which is comparable to the optimal solutions.

To apply lift-based and lift-inverse measures to the subset merging algorithm, we replace $\mathsf{\Lambda }\left(y\right)$ and $\mathsf{\Psi }\left(y\right)$ in (6) and Algorithm 1, with the corresponding lift-based and lift-inverse measures in Definitions 5 and 6, respectively. For example, ${\mathcal{X}}_L$ and ${\mathcal{X}}_H$ for the $\alpha$-lift are obtained as

$$\begin{array}{c}{\mathcal{X}}_L\triangleq \{x\in \mathcal{X}:{\mathsf{\Psi }}_{\alpha }^S\left(x\right)\le {\mathrm{e}}^{{\epsilon }_l}and{\mathsf{\Lambda }}_{\alpha }^S\left(x\right)\le {\mathrm{e}}^{{\epsilon }_u}\}and{\mathcal{X}}_H=\mathcal{X}\backslash {\mathcal{X}}_L.\end{array}$$

(37)

The privacy risk measure in Algorithm 1 is also given by $\omega \left(x\right)={\mathsf{\Psi }}_{\alpha }^S\left(x\right)+{\mathsf{\Lambda }}_{\alpha }^S\left(x\right)$. We compare the PUT of lift-based and lift-inverse privacy with (${\epsilon }_l,{\epsilon }_u$)-ALIP, where lift-based and lift-inverse measures are bounded as follows:

• ${\ell }_1$-privacy: ${\mathsf{\Lambda }}_{{\ell }_1}\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u}-1$          and ${\mathsf{\Psi }}_{{\ell }_1}\left(y\right)\le {\mathrm{e}}^{{\epsilon }_l}-1,\forall y\in \mathcal{Y}.$
• ${\chi }^2$-privacy: ${\mathsf{\Lambda }}_{{\chi }^2}\left(y\right)\le {({\mathrm{e}}^{{\epsilon }_u}-1)}^2$    and ${\mathsf{\Psi }}_{{\chi }^2}\left(y\right)\le {({\mathrm{e}}^{{\epsilon }_l}-1)}^2, \forall y\in \mathcal{Y}.$
• $\alpha$-lift-privacy: ${\mathsf{\Lambda }}_{\alpha }^S\left(y\right)\le {\mathrm{e}}^{{\epsilon }_u}$              and ${\mathsf{\Psi }}_{\alpha }^S\left(y\right)\le {\mathrm{e}}^{{\epsilon }_l},\forall y\in \mathcal{Y}.$

We apply the subset merging mechanism with the simulation setup in Section 3.1.3. Figure 11 and Figure 12 demonstrate the PUT of ALIP for $\lambda =0.5$ and ${\ell }_1$ and ${\chi }^2$ privacy for $\lambda =\{0.5,0.65\}$ for synthetic and Adult dataset, respectively. When $\lambda =0.5$, ${\ell }_1$ and ${\chi }^2$ privacy result in higher utility compared to ALIP for all values of $\epsilon$ since lift-based and lift-inverse measures are relaxations of max- and min-lift. To observe the effect of the asymmetric scenario, we depict ${\ell }_1$ and ${\chi }^2$ privacy for $\lambda =0.65$. From Figure 11a and Figure 12a, we observe that lift-inverse relaxation ($\lambda =0.65$) enhances utility significantly for $\epsilon >1$, but worsens utility for $\epsilon <1$. The reason is that when $\epsilon <1$, lift-inverse privacy constraint in the asymmetric scenario is strict, which requires more symbols to be merged in each subset and causes larger subsets and utility degradation.

A comparison between $\alpha$-lift privacy and ALIP for synthetic data is shown in Figure 13 for $\alpha \in \{2,10,100\}$. $\alpha$-lift privacy is tunable such that when $\alpha =\infty$, it is equivalent to ALIP, and when $\alpha <\infty$, it results in a relaxation scenario. We observe tunable property in Figure 13 where $\alpha =2$ has the highest utility. Moreover, when $\alpha$ increases, the PUT of $\alpha$-lift privacy becomes closer to ALIP.

7. Conclusions

In this paper, we studied lift, the likelihood ratio between posterior and prior belief about sensitive features in a dataset. We demonstrated the distinction between the min- and max-lifts in terms of data privacy concerns. We proposed ALIP as a generalised version of LIP to have a more compatible notion of privacy with lift asymmetry. ALIP can enhance utility in the watchdog and ORR mechanisms, two main approaches to achieve lift-based privacy. We proposed two subset randomisation methods to enhance the utility of the watchdog mechanism and reduce ORR complexity for large datasets. We also investigated the existing lift-based measures, showing that they could incur significant leakage on the min-lift. Thus, we proposed lift-inverse measures to restrict the min-lift leakage. Finally, we applied the watchdog mechanism to study the PUT of lift-based and lift-inverse measures. For future work, one can consider the applicable operational meaning of the min-lift and max-lift. Subset randomisation can be applied to decrease the complexity and enhance the utility of other privacy mechanisms. Moreover, optimal randomisation for $\alpha$-lift is also unknown and could be considered.