Variable-Length Coding with Zero and Non-Zero Privacy Leakage ^†

Abstract

A private compression design problem is studied, where an encoder observes useful data Y, wishes to compress them using variable-length code, and communicates them through an unsecured channel. Since Y are correlated with the private attribute X, the encoder uses a private compression mechanism to design an encoded message $\mathcal{C}$ and sends it over the channel. An adversary is assumed to have access to the output of the encoder, i.e., $\mathcal{C}$, and tries to estimate X. Furthermore, it is assumed that both encoder and decoder have access to a shared secret key W. In this work, the design goal is to encode message $\mathcal{C}$ with the minimum possible average length that satisfies certain privacy constraints. We consider two scenarios: 1. zero privacy leakage, i.e., perfect privacy (secrecy); 2. non-zero privacy leakage, i.e., non-perfect privacy constraint. Considering the perfect privacy scenario, we first study two different privacy mechanism design problems and find upper bounds on the entropy of the optimizers by solving a linear program. We use the obtained optimizers to design $\mathcal{C}$. In the two cases, we strengthen the existing bounds: 1. $|\mathcal{X}|\ge |\mathcal{Y}|$; 2. The realization of $(X,Y)$ follows a specific joint distribution. In particular, considering the second case, we use two-part construction coding to achieve the upper bounds. Furthermore, in a numerical example, we study the obtained bounds and show that they can improve existing results. Finally, we strengthen the obtained bounds using the minimum entropy coupling concept and a greedy entropy-based algorithm. Considering the non-perfect privacy scenario, we find upper and lower bounds on the average length of the encoded message using different privacy metrics and study them in special cases. For achievability, we use two-part construction coding and extended versions of the functional representation lemma. Lastly, in an example, we show that the bounds can be asymptotically tight.

1. Introduction

In this work, the random variable (RV) Y denotes the useful data and is correlated with the private data denoted by RV X. An encoder wishes to compress Y and communicates it to a user over an unsecured channel. The encoded message is denoted by the RV $\mathcal{C}$. As shown in Figure 1, it is assumed that an adversary has access to the encoded message $\mathcal{C}$, and wants to extract information about X. Moreover, it is assumed that the encoder and decoder have access to a shared secret key denoted by the RV W with size M. The goal is to design an encoded message $\mathcal{C}$, which compresses Y, using a variable-length code with the minimum possible average length that satisfies certain privacy constraints. We utilize techniques used in privacy mechanism and compression design problems and combine them to build such a code $\mathcal{C}$. In this paper, we introduce an approach and apply it to a lossless compression problem.

In this paper, we consider two scenarios, where the privacy leakage is either zero or a bounded leakage is allowed. We refer to these scenarios as perfect and non-perfect privacy scenarios. In the perfect privacy scenario, considering two different cases, we extend previously existing results [1,2]. In the non-perfect privacy scenario, we extend previously existing results [1,2] by generalizing the perfect privacy constraint and allowing non-zero leakage. We use different privacy leakage constraints, e.g., the mutual information between X and $\mathcal{C}$ equals $ϵ$, a strong privacy constraint, and bounded per-letter privacy criterion.

1.1. Related Works

Recently, the compression and privacy mechanism design problems have received increased attention [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]. Specifically, in [3], the notion of perfect secrecy was introduced by Shannon, where the public data and private data are statistically independent. Equivocation as a measure of information leakage for information theoretic security was used in [4,5,6]. A rate-distortion approach to information theoretic secrecy was studied in [11]. Maximal leakage was introduced in [12] and used in [13] for the Shannon cipher system. Furthermore, bounds on the privacy–utility trade-off have been derived. The fundamental limits of the privacy–utility trade-off when measuring privacy leakage using estimation-theoretic guarantees were studied in [7]. A privacy mechanism design with total variation as a privacy measure was studied in [8]. A source coding problem with secrecy was studied in [10]. The concept of a privacy funnel was introduced in [14], where the privacy–utility trade-off was studied considering the log-loss as privacy measure and a distortion measure for utility. In both [6,10], privacy–utility trade-offs considering equivocation and expected distortion as measures of privacy and utility were studied.

In [15], the problem of privacy–utility trade-off considering mutual information as measures of both privacy and utility was studied. It was shown that, under perfect privacy, the privacy mechanism design problem can be obtained using a linear program. This was generalized in [25] considering a privacy–utility trade-off with a rate constraint. Moreover, in [15], it was shown that non-zero information about useful data Y can be revealed if the kernel (leakage matrix) between private and useful data is not invertible. In [16], the work of [15] was extended by relaxing the perfect privacy assumption, allowing some small bounded privacy leakage. Specifically, privacy mechanisms with a per-letter (point-wise) privacy criterion considering an invertible kernel were designed, allowing a small leakage. This result was extended to a non-invertible leakage matrix in [17].

In [1], an approach to partial secrecy called secrecy by design was introduced and applied to two information processing problems: privacy mechanism design and lossless compression. For the privacy design problem, bounds on the privacy–utility trade-off were derived using the functional representation lemma. These results were obtained under a perfect privacy (secrecy) assumption. In [18], the privacy problems considered in [1] were extended by relaxing the perfect secrecy constraint and allowing some leakages. In [20], a privacy–utility trade-off with two different per-letter (point-wise) privacy constraints was studied. The fundamental limits of private data disclosure were studied in [26], where the goal was to minimize the leakage under the utility constraints with non-specific tasks, and it was shown that, under the assumption that the private data are an element-wise deterministic function of useful data, the main problem can be reduced to multiple privacy funnel (PF) problems. Furthermore, the exact solution to each problem was obtained. The concept of lift was studied in [27], which represents the likelihood ratio between the posterior and prior beliefs concerning sensitive features within a dataset. Further privacy leakage measures, such as the differential privacy introduced in [28], $(ϵ,\delta )$-differential privacy [29], local differential privacy [30,31,32,33], maximal leakage [12], and lift [27], have been used in the literature.

Moreover, in [1], the problems of fixed-length and variable-length compression were studied, and upper and lower bounds on the average length of an encoded message were derived. These results were obtained under the assumption that the private data were independent of the encoded message, which corresponds to perfect privacy. The minimum entropy coupling concept and a greedy entropy-based algorithm were studied in [34,35,36]. More specifically, in [36], an information spectrum converse was derived and used to find a lower bound on the minimum entropy problem.

1.2. Our Contributions

In the perfect privacy scenario, we consider the problem in [1], where for the problem of lossless data compression, strong information theoretic guarantees are provided and fundamental limits are characterized when the private data are a deterministic function of the useful data. In this paper, we improve the bounds obtained in [1].

To this end, we combine the privacy design techniques used in [18], which are based on extended versions of the functional representation lemma (FRL) and strong functional representation lemma (SFRL), as well as the lossless data compression design in [1]. We find lower and upper bounds on the average length of the encoded message $\mathcal{C}$ and study them in different scenarios. Considering a specific set of joint distributions for $(X,Y)$, we propose an algorithm with low complexity to find bounds on the optimizer of privacy problems in [18] with zero leakage. We use the obtained results to design $\mathcal{C}$, which achieves tighter bounds compared to [1]. Furthermore, when $|\mathcal{X}|\ge |\mathcal{Y}|$, we propose a new code that improves on the bounds in [1]. We propose a new design and strengthen the obtained bounds using the minimum entropy coupling concept and a greedy entropy-based algorithm. Finally, in a numerical example, we study the bounds and compare them with [1].

In the non-perfect privacy scenario, our problem is closely related to [1], where we generalize the variable-length lossless compression problem considered in [1] by removing the assumption that X and $\mathcal{C}$ are independent, i.e., $I(X;\mathcal{C}(Y,W))=0$, and therefore allowing a small leakage.

We find the lower and upper bounds on the average length of the encoded message $\mathcal{C}$ and study them in different scenarios. For achievability, we use two-part construction coding. In an example, we show that the obtained bounds can be asymptotically tight. Furthermore, in the case of perfect privacy, the existing bounds found in [1] were improved considering the case where $X=(X_1,X_2)$ and $X_2$ is a deterministic function of $X_1$. The conference versions regarding this paper can be found in [22,23].

Our contribution can be summarized as follows:

(i) In Section 2, we define a private variable-length coding with zero and non-zero leakage problems. We propose a method to deal with the privacy concerns and present privacy–utility trade-offs considering zero and non-zero leakage scenarios.

(ii) In Section 3, we provide a brief overview of the privacy problems in the literature, two essential lemmas, and the minimum entropy coupling concept.

(iii) In Section 4, we find the upper and lower bounds on the trade-offs proposed in Section 2 considering zero and non-zero leakage scenarios. In both scenarios, to find upper bounds, we use the two-part construction coding introduced in [1], which is based on the extended versions of the FRL, the SFRL. We obtain a simple private compression mechanism design that can be optimal in specific scenarios. Moreover, we provide a discussion and comparison of the obtained bounds, with each other and the literature, and the tightness of the bounds is investigated. The results regarding the tightness of the bounds are extended using the concept of the minimum information coupling problem in a zero leakage scenario.

(iv) In Section 5, we present an application in which our method can be applied. Specifically, we consider a cache-aided network and discuss how our results in this paper can be used.

(v) In Section 6, we present an experiment considering the MNIST dataset and we compare our method with previous results in the literature.

Finally, the paper is concluded in Section 7.

2. System Model and Problem Formulation

Let $P_{XY}$ denote the joint distribution of discrete random variables X and Y defined on alphabets $\mathcal{X}$ and $\mathcal{Y}$. We assume that the cardinality $|\mathcal{X}|$ is finite and $|\mathcal{Y}|$ is finite or countably infinite. We represent $P_{XY}$ by a matrix defined on ${\mathbb{R}}^{|\mathcal{X}|\times |\mathcal{Y}|}$ and marginal distributions of X and Y by vectors $P_X$ and $P_Y$ defined on ${\mathbb{R}}^{|\mathcal{X}|}$ and ${\mathbb{R}}^{|\mathcal{Y}|}$ given by the row and column sums of $P_{XY}$. The relation between X and Y is given by the leakage matrix $P_{X|Y}$ defined on ${\mathbb{R}}^{|\mathcal{X}|\times |\mathcal{Y}|}$. The shared secret key is denoted by the discrete RV W defined on $\{1,\dots ,M\}$ and is assumed to be accessible by both the encoder and decoder. Furthermore, we assume that W is uniformly distributed and is independent of X and Y. A prefix-free code with variable-length and shared secret key of size M is a pair of mappings:

$$\begin{array}{c}\hfill (\mathrm{encoder})\mathcal{C}:\mathcal{X}\times \mathcal{Y}\times \{1,\dots ,M\}\to {\{0,1\}}^{\ast }\\ \hfill (\mathrm{decoder})\mathcal{D}:{\{0,1\}}^{\ast }\times \{1,\dots ,M\}\to \mathcal{Y}.\end{array}$$

The output of the encoder $\mathcal{C}(Y,W)$ describes the encoded message. The variable-length code $(\mathcal{C},\mathcal{D})$ is lossless if

$$\begin{array}{c}\hfill \mathbb{P}(\mathcal{D}(\mathcal{C}(X,Y,W),W)=Y)=1.\end{array}$$

(1)

2.1. Non-Zero Privacy Leakage (Non-Perfect Privacy)

Similarly to [1], we define $ϵ$-private, strongly $ϵ$-private, and point-wise $ϵ$-private codes. The code $(\mathcal{C},\mathcal{D})$ is ϵ-private if

$$\begin{array}{c}\hfill I(\mathcal{C}(X,Y,W);X)=ϵ.\end{array}$$

(2)

Moreover, the code $(\mathcal{C},\mathcal{D})$ is bounded ϵ-private if

$$\begin{array}{c}\hfill I(\mathcal{C}(X,Y,W);X)\le ϵ.\end{array}$$

(3)

Let $\xi$ be the support of $\mathcal{C}(X,W,Y)$. For any $c\in \xi$, let $\mathbb{L}(c)$ be the length of the codeword. The code $(\mathcal{C},\mathcal{D})$ is of $(\alpha ,M)$-variable-length if

$$\begin{array}{c}\hfill \mathbb{E}(\mathbb{L}(\mathcal{C}(X,Y,w)))\le \alpha ,\forall w\in \{1,\dots ,M\}.\end{array}$$

(4)

Finally, let us define the sets ${\mathcal{H}}^{ϵ}(\alpha ,M)$ and ${\mathcal{H}}_b^{ϵ}(\alpha ,M)$, as follows: ${\mathcal{H}}^{ϵ}(\alpha ,M)\triangleq \{(\mathcal{C},\mathcal{D}):(\mathcal{C},\mathcal{D})\mathrm{is}ϵ\text{-private}\mathrm{and}\mathrm{of}(\alpha ,M)\text{-variable-length}\}$, and ${\mathcal{H}}_b^{ϵ}(\alpha ,M)\triangleq \{({\mathcal{C}}^{\prime },{\mathcal{D}}^{\prime }):({\mathcal{C}}^{\prime },{\mathcal{D}}^{\prime })\mathrm{is}\mathrm{bounded}ϵ\text{-private}\mathrm{and}\mathrm{of}(\alpha ,M)\text{-variable-length}\}$. The private compression design problems can be then stated as follows:

$$\begin{array}{cc}\hfill \mathbb{L}(P_{XY},M,ϵ)& =\underset{\begin{array}{c}\begin{array}{c}(\mathcal{C},\mathcal{D}):(\mathcal{C},\mathcal{D})\in {\mathcal{H}}^{ϵ}(\alpha ,M)\end{array}\end{array}}{inf}\alpha ,\hfill \end{array}$$

(5)

$$\begin{array}{cc}\hfill {\mathbb{L}}^b(P_{XY},M,ϵ)& =\underset{\begin{array}{c}\begin{array}{c}(\mathcal{C},\mathcal{D}):(\mathcal{C},\mathcal{D})\in {\mathcal{H}}_b^{ϵ}(\alpha ,M)\end{array}\end{array}}{inf}\alpha .\hfill \end{array}$$

(6)

Clearly, we have ${\mathbb{L}}^b(P_{XY},M,ϵ)\le \mathbb{L}(P_{XY},M,ϵ)$ and ${\mathbb{L}}^b(P_{XY},M,ϵ)\le \mathbb{L}(P_{XY},M,0)$.

Remark 1.

Considering $ϵ=0$, both (5) and (6) lead to the privacy–compression rate trade-off studied in [1]. In this paper, we generalize this trade-off by considering a non-zero $ϵ$.

2.2. Zero Privacy Leakage (Perfect Privacy)

We define a perfectly-private code. The code $(\mathcal{C},\mathcal{D})$ is perfectly-private if

$$\begin{array}{c}\hfill I(\mathcal{C}(X,Y,W);X)=0.\end{array}$$

(7)

Let $\xi$ be the support of $\mathcal{C}(X,W,Y)$ and for any $c\in \xi$ let $\mathbb{L}(c)$ be the length of the codeword. The code $(\mathcal{C},\mathcal{D})$ is $(\alpha ,M)$-variable-length if (4) holds. Finally, let us define the sets $\mathcal{H}(\alpha ,M)$ as follows:

$\mathcal{H}(\alpha ,M)\triangleq \{(\mathcal{C},\mathcal{D}):(\mathcal{C},\mathcal{D})\mathrm{is}\text{perfectly-private}\mathrm{and}(\alpha ,M)\text{-variable-length}\}$. The private compression design problems can be stated as follows:

$$\begin{array}{cc}\hfill {\mathbb{L}}^0(P_{XY},M)& =\underset{\begin{array}{c}\begin{array}{c}(\mathcal{C},\mathcal{D}):(\mathcal{C},\mathcal{D})\in \mathcal{H}(\alpha ,M)\end{array}\end{array}}{inf}\alpha .\hfill \end{array}$$

(8)

Furthermore, let us recall the privacy mechanism design problems considered in [19] with zero leakage as follows:

$$\begin{array}{cc}\hfill g_0(P_{XY})& \triangleq \underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y}:X-Y-U\\ I(U;X)=0,\end{array}\end{array}}{max}I(Y;U),\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill h_0(P_{XY})& \triangleq \underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y,X}:I(U;X)=0,\end{array}\end{array}}{max}I(Y;U).\hfill \end{array}$$

(10)

Finally, we define a set of joint distributions ${\widehat{\mathcal{P}}}_{XY}$ as follows:

$$\begin{array}{c}\hfill {\widehat{\mathcal{P}}}_{XY}\triangleq \{P_{XY}:g_0(P_{XY})=h_0(P_{XY})\}.\end{array}$$

(11)

Remark 2.

The problem (8) was studied in [1]. Here, we improve the bounds in [1] in two different cases and obtain more bounds using the concept of the minimum information coupling problem.

3. Preliminaries and Overview of the Privacy Problems

In this section, we provide a brief overview of a few related privacy problems. We then provide essential lemmas and definitions corresponding to the extended functional representation lemma, the extended strong functional representation lemma, and the minimum information coupling problem. Mutual information has been widely used as a privacy leakage measure [1,2,14,15,18,21,26]. Specifically, in [21], the following problem was addressed

$$\begin{array}{cc}\hfill g_{ϵ}(P_{XY})& \triangleq \underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y}:X-Y-U\\ I(U;X)\le ϵ,\end{array}\end{array}}{sup}I(Y;U),\hfill \end{array}$$

(12)

where in ([21], Lemma 1), the lower and upper bounds on $g_{ϵ}(P_{XY})$ were derived. Considering perfect privacy, i.e., $ϵ=0$, $g_0(P_{XY})$ can be obtained by solving a linear program ([15], Theorem 1). This implies that the optimal mapping is the solution to a linear program. Furthermore, it has been shown that, to find the optimal privacy-preserving mapping, it is sufficient to consider U such that $|\mathcal{U}|\le \mathrm{null}(P_{X|Y})+1$. However, solving the linear program suggested by [15] can become challenging when the size of $\mathcal{Y}$ or $\mathcal{X}$ increases. Necessary and sufficient conditions for achieving non-zero utility when the private data are hidden, i.e., $g_0(P_{XY})>0$, were derived in [37,38]. It was shown that $g_0(P_{XY})>0$ if and only if the rows of $P_{X|Y}$ are linearly dependent. This result was demonstrated and generalized in [15], e.g., see ([15], Proposition 1). Moreover, considering an observable private data scenario, necessary and sufficient conditions for attaining non-zero utility, i.e., $h_0(P_{XY})>0$, were derived in ([1], Theorem 5), where

$$\begin{array}{cc}\hfill h_{ϵ}(P_{XY})& \triangleq \underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y,X}:I(U;X)\le ϵ,\end{array}\end{array}}{sup}I(Y;U).\hfill \end{array}$$

(13)

It has been shown that $h_0(P_{XY})>0$ if and only if Y is not a deterministic function of X, i.e., $H(Y|X)>0$.

Next, we present a brief overview of the linear program proposed by [15] that attains $g_0(P_{XY})$. To do so, let $\beta$ be a vector in ${\mathbb{R}}^{|\mathcal{Y}|}$. It is shown that $\beta \in \mathrm{Null}(P_{X|Y})$ if and only if $\beta \in \mathrm{Null}(M)$, where $M\in {\mathbb{R}}^{|\mathcal{X}|\times |\mathcal{Y}|}$ is constructed as follows: Let V be the matrix of right eigenvectors of $P_{X|Y}$, i.e., $P_{X|Y}=U\Sigma V^T$ and $V=[v_1,v_2,\dots ,v_{|\mathcal{Y}|}]$, then M is defined as

$$\begin{array}{c}\hfill M\triangleq {\left[v_1,v_2,\dots ,v_{\mathrm{rank}(P_{X|Y})}\right]}^T.\end{array}$$

Furthermore, if $\beta \in \mathrm{Null}(P_{X|Y})$, then $1^T\beta =0$. As shown in [15], for every $u\in \mathcal{U}$, if the Markov chain $X-Y-U$ holds and $I(X;U)=0$, then the vector $P_{Y|U=u}$ belongs to the following convex polytope $\mathbb{S}$

$$\begin{array}{c}\hfill \mathbb{S}=\left\{y\in {\mathbb{R}}^{|\mathcal{Y}|}|My=M{P}_Y,y\ge 0\right\}.\end{array}$$

Using this, we have

$$\begin{array}{c}\hfill X-Y-U,I(X;U)=0\leftrightarrow P_{Y|U=u}\in \mathbb{S},\forall u,\end{array}$$

(14)

which results in the following equivalency

$$\begin{array}{c}\hfill \underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y}:X-Y-U\\ I(X;U)=0\end{array}\end{array}}{min}H(Y|U)=\underset{\begin{array}{c}\begin{array}{c}{P}_U,P_{Y|U=u}\in \mathbb{S},\forall u\in \mathcal{U},\\ {\sum }_u{P}_U(u)P_{Y|U=u}=P_Y,\end{array}\end{array}}{min}H(Y|U),\end{array}$$

(15)

where $P_U$ defined on ${\mathbb{R}}^{|\mathcal{U}|}$ is the marginal distribution of U. Finally, let $P_{Y|U=u}^{\ast },\forall u\in \mathcal{U}$ be the minimizer of $H(Y|U)$ over the set $\{P_{Y|U=u}\in \mathbb{S},\forall u\in \mathcal{U}|{\sum }_u{P}_U(u)P_{Y|U=u}=P_Y\}$, then, $P_{Y|U=u}^{\ast }\in \mathbb{S}$ for all $u\in \mathcal{U}$ must belong to the extreme points of ${\mathbb{S}}_u$. Furthermore, it is sufficient to consider $\mathrm{null}(P_{X|Y})+1$ extreme points of $\mathbb{S}$. Using the previous result, the solution to the minimization in (15) can be obtained in two phases: in phase one, the extreme points of set $\mathbb{S}$ are identified, while in phase two, proper weights over these extreme points are obtained to minimize the objective function. As argued in [15], the extreme points of $\mathbb{S}$ are the basic feasible solutions of $\mathbb{S}$. Basic feasible solutions of $\mathbb{S}$ can be found in the following manner. Let $\Omega$ be the set of indices which correspond to $\mathrm{rank}(P_{X|Y})$ linearly independent columns of M, i.e., $|\Omega |=\mathrm{rank}(P_{X|Y})$ and $\Omega \subset \{1,\dots ,|\mathcal{Y}|\}$. Let $M_{\Omega }\in {\mathbb{R}}^{\mathrm{rank}(P_{X|Y})\times \mathrm{rank}(P_{X|Y})}$ be the sub-matrix of M with columns indexed by the set $\Omega$. Then, if all elements of the vector $M_{\Omega }^{-1}M{P}_Y$ are non-negative, the vector $V_{\Omega }^{\ast }\in {\mathbb{R}}^{|\mathcal{Y}|}$, which is defined in the following, is a basic feasible solution of $\mathbb{S}$. Assume that $\Omega =\{{\omega }_1,\dots ,{\omega }_{\mathrm{rank}(P_{X|Y})}\}$, where ${\omega }_i\in \{1,\dots ,|\mathcal{Y}|\}$ and all elements are arranged in an increasing order. The ${\omega }_i$-th element of $V_{\Omega }^{\ast }$ is defined as the i-th element of $M_{\Omega }^{-1}M{P}_Y$, i.e., for $1\le i\le \mathrm{rank}(P_{X|Y})$, we have

$$\begin{array}{c}\hfill V_{\Omega }^{\ast }({\omega }_i)=\left(M_{\Omega }^{-1}M{P}_Y\right)(i).\end{array}$$

(16)

The other elements of $V_{\Omega }^{\ast }$ are set to zero. Thus, by using the same arguments as in [15], we obtain the following corollary.

Corollary 1.

Let ${\mathbb{S}}^{\ast }$ be a set that contains the extreme points of $\mathbb{S}$. If all elements of the vector $M_{\Omega }^{-1}M{P}_Y$ are non-negative, then $V_{\Omega }^{\ast }\in {\mathbb{S}}^{\ast }\subseteq \mathbb{S}$.

In the next proposition, we show two properties of each vector inside ${\mathbb{S}}^{\ast }$.

Proposition 1.

Let $\Omega \subset \{1,\dots ,|\mathcal{Y}|\},|\Omega |=\mathit{rank}(P_{X|Y})$. For every Ω, we have $1^T\left(M_{\Omega }^{-1}M{P}_Y\right)=1$.

Proof. 

Consider the set ${\mathbb{S}}^1=\{y\in {\mathbb{R}}^{|\mathcal{Y}|}|My=M{P}_Y\}$. Any element in ${\mathbb{S}}^1$ has sum elements equal to one, since we have $M(y-P_Y)=0\Rightarrow y-P_Y\in \mathrm{Null}(P_{X|Y})$, we obtain $1^T(y-P_Y)=0\Rightarrow 1^{T}y=1$. The basic solutions of ${\mathbb{S}}^1$ are $W_{\Omega }^{\ast }$ defined as follows: Let $\Omega =\{{\omega }_1,\dots ,{\omega }_{\mathrm{rank}(P_{X|Y})}\}$, where ${\omega }_i\in \{1,\dots ,|\mathcal{Y}|\}$, then, $W_{\Omega }^{\ast }({\omega }_i)=M_{\Omega }^{-1}M{P}_Y(i),$ and other elements of $W_{\Omega }^{\ast }$ are zero. Thus, the sum over all elements of $M_{\Omega }^{-1}M{P}_Y$ equals one, since each element in ${\mathbb{S}}^1$ has to sum to one.  □

After finding all extreme points of the set $\mathbb{S}$, for the second phase, we proceed as follows. Assume that all extreme points of the set $\mathbb{S}$ are denoted by ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_K$, which were obtained in the first phase. Then, using the equivalency in Theorem (15), we have

$$\begin{array}{cc}\hfill & g_0(P_{XY})=H(Y)-\underset{\begin{array}{c}\begin{array}{c}\beta :\\ \beta \in {\mathbb{R}}^K,\beta \ge 0\\ [{\alpha }_1{\alpha }_2\dots {\alpha }_K]\beta =P_Y\end{array}\end{array}}{min}[H({\alpha }_1)H({\alpha }_2)\dots H({\alpha }_K)]\beta ,\hfill \end{array}$$

(17)

where $H({\alpha }_i)$ is the entropy of the distribution vector ${\alpha }_i$.

In this work, considering the zero leakage scenario, to design the code, we use the properties of the privacy problems defined in (12) and (13).

Next, we recall two important lemmas from [18].

Lemma 1.

(Extended Functional Representation Lemma (EFRL)): For a pair of RVs $(X,Y)$ distributed according to $P_{XY}$ supported on alphabets $\mathcal{X}$ and $\mathcal{Y}$, respectively, where $|\mathcal{X}|$ is finite and $|\mathcal{Y}|$ is finite or countably infinite, and any $0\le ϵ<I(X;Y)$, there exists a RV U defined on $\mathcal{U}$ such that the leakage between X and U is equal to ϵ, i.e., we have

$$\begin{array}{c}\hfill I(U;X)=ϵ,\end{array}$$

Y is a deterministic function of $(U,X)$, i.e., we have

$$\begin{array}{c}\hfill H(Y|U,X)=0,\end{array}$$

and $|\mathcal{U}|\le \left[|\mathcal{X}|(|\mathcal{Y}|-1)+1\right]\left[|\mathcal{X}|+1\right].$

Lemma 2.

(Extended Strong Functional Representation Lemma (ESFRL)): For a pair of RVs $(X,Y)$ distributed according to $P_{XY}$ supported on alphabets $\mathcal{X}$ and $\mathcal{Y}$, respectively, where $|\mathcal{X}|$ is finite and $|\mathcal{Y}|$ is finite or countably infinite with $I(X,Y)<\infty$, and any $0\le ϵ<I(X;Y)$, there exists a RV U defined on $\mathcal{U}$ such that the leakage between X and U is equal to ϵ, i.e., we have

$$\begin{array}{c}\hfill I(U;X)=ϵ,\end{array}$$

Y is a deterministic function of $(U,X)$, i.e., we have

$$\begin{array}{c}\hfill H(Y|U,X)=0,\end{array}$$

$I(X;U|Y)$ can be upper bounded as follows:

$$\begin{array}{c}\hfill I(X;U|Y)\le \alpha H(X|Y)+(1-\alpha )\left[log(I(X;Y)+1)+4\right],\end{array}$$

and $|\mathcal{U}|\le \left[|\mathcal{X}|(|\mathcal{Y}|-1)+2\right]\left[|\mathcal{X}|+1\right],$ where $\alpha ={\displaystyle \frac{ϵ}{H(X)}}$.

The main idea in constructing U, which satisfies the conditions in Lemmas 1 and 2, is to add a randomized response to the output of the FRL and SFRL, respectively. The output refers to a random variable which is produced by the FRL or the SFRL and satisfies the corresponding constraints. In this work, considering the non-zero leakage scenario, to design the code, we utilize the techniques used in Lemmas 1 and 2. The randomization technique was used in finding fair and private representations of a dataset in [39]. To find fair representations, we use randomization techniques similar to those in Lemmas 1 and 2, which lead to lower bounds. Furthermore, this randomization technique has also been applied in the design of differentially private mechanisms [40,41,42,43]. A similar randomization technique was used in [22,23] to address private compression design problems. Next, we recall the important results regarding the upper and lower bounds on the minimum entropy coupling as obtained in [34,35,36]. First, we recall the definition of the minimum entropy coupling problem using ([36], Def. 2).

Definition 1.

(minimum entropy coupling) For a set of PMFs $\{P_1,\dots ,P_M\}$, the minimum Shannon entropy coupling is

$$\begin{array}{c}\hfill H^{\ast }(P_1,\dots ,P_M)\triangleq \underset{P_{Y_1,\dots ,Y_M}:Y_i\sim P_i,\forall i}{inf}H(Y_1,\dots ,Y_M),\end{array}$$

(18)

where the infimum is taken over all the joint distributions $P_{Y_1,\dots ,Y_M}$, where the marginal distribution $P_{Y_i}$ equals $P_i$ for all $i\in \{1,\dots ,M\}$.

Similarly to [36], for a given joint distribution $P_{XY}$, let the minimum entropy of functional representation of $(X,Y)$ be defined as

$$\begin{array}{c}\hfill H^{\ast }(P_{XY})\triangleq \underset{\begin{array}{c}\begin{array}{c}H(Y|X,U)=0,I(X;U)=0\end{array}\end{array}}{inf}H(U).\end{array}$$

(19)

Remark 3.

As shown in ([36], Lemma 1), the minimum entropy functional representation and the minimum entropy coupling are related functions. In more detail, $H^{\ast }(P_{XY})$ equals the minimum entropy coupling of the set of PMFs $\{P_{Y|X=x_1},\dots ,P_{Y|X=x_n}\}$, where $\mathcal{X}=\{x_1,\dots ,x_n\}$.

Let ${\mathcal{G}}_S$ be the output of the greedy entropy-based algorithm which was proposed in ([34], Section 3), i.e., $H^{\ast }(P_{XY})\le H({\mathcal{G}}_S)$. More specifically, the corresponding algorithm aims to solve (19) but does not achieve the optimal solution in general. Next, we recall a result obtained in [35], which showed that ${\mathcal{G}}_S$ is optimal within ${\displaystyle \frac{loge}{e}}\approx 0.53$ bits when $|\mathcal{X}|=2$ and is optimal within ${\displaystyle \frac{1+loge}{2}}\approx 1.22$ bits when $|\mathcal{X}|>2$. Let $U^{\ast }$ achieve the optimal solution of (19), i.e., $H(U^{\ast })=H^{\ast }(P_{XY})$.

Theorem 1

([35], Th. 3.4, Th. 4.1, Th. 4.2). Let $(X,Y)\sim P_{XY}$ and have finite alphabets. When X is binary, we have

$$\begin{array}{cc}\hfill H(Profile)& \le H(U^{\ast })\le H({\mathcal{G}}_S)\le H(Profile)+{\displaystyle \frac{loge}{e}}\hfill \\ & \approx H(Profile)+0.53.\hfill \end{array}$$

(20)

Moreover, for $|\mathcal{X}|>2$, we have

$$\begin{array}{cc}\hfill H(Profile)& \le H(U^{\ast })\le H({\mathcal{G}}_S)\hfill \\ & \le H(Profile)+{\displaystyle \frac{1+loge}{2}}\hfill \\ & \approx H(Profile)+1.22.\hfill \end{array}$$

(21)

Here, $Profile$ corresponds to the profile method proposed in ([35], Section 3).

Since finding the optimal solution for (19) is challenging, Theorem 1 asserts that ${\mathcal{G}}_S$ can be a good approximation for $U^{\ast }$ that achieves (19). Next, we present the results on lower bounds on $H^{\ast }(P_{XY})$ obtained in a parallel work [36]. The lower bounds were derived using information spectrum and majorization concepts.

Theorem 2

([36], Corollary 2, Th. 2). Let $(X,Y)\sim P_{XY}$ and have finite alphabets. Let $\alpha =1$ in ([36], Corollary 2, Th. 2). We have

$$\begin{array}{c}\hfill H({\wedge }_{x\in \mathcal{X}}{P}_{Y|x})\le H(Q^{\ast })\le H(U^{\ast }),\end{array}$$

(22)

where ∧ corresponds to the greatest lower bound with respect to majorization and $Q^{\ast }$ is defined in ([36], Lemma 3).

Remark 4.

In contrast with [35], the lower bounds in [36] were obtained using Rényi entropy in (19). In this work, we consider Shannon entropy, which is a special case of Rényi entropy.

Remark 5.

As argued in ([36], Remark 1), for $\alpha =1$ the (largest) lower bounds obtained in [35,36] match. Thus, using Theorem 1, for binary X, we have

$$\begin{array}{c}\hfill H(Q^{\ast })\le H(U^{\ast })\le H({\mathcal{G}}_S)\le H(Q^{\ast })+{\displaystyle \frac{loge}{e}},\end{array}$$

(23)

and for $|\mathcal{X}|>2$,

$$\begin{array}{cc}\hfill H(Q^{\ast })& \le H(U^{\ast })\le H({\mathcal{G}}_S)\le H(Q^{\ast })+{\displaystyle \frac{1+loge}{2}}.\hfill \end{array}$$

(24)

Moreover, in some cases, the lower bound $H(Q^{\ast })$ is tight, e.g., see ([36], Example 2).

As discussed in [36], $Q^{\ast }$ can be obtained by a greedy construction. To do so, let $Q^{\ast }=(q_1^{\ast },q_2^{\ast },\dots )$ with $q_1^{\ast }\ge q_2^{\ast }\ge \dots$, where $q_i=P(Q=q_i)$. Let $P_{Y|X}$ be a matrix with columns $P_{Y|X=x}$, where each is a conditional distribution vector and assume that each column has a descending order (re-order each column). Let $q_1^{\ast }={min}_{x\in \mathcal{X}}\left\{{max}_{y\in \mathcal{Y}}{P}_{Y|X}(y|x)\right\}$. In other words, we choose the smallest number in the first row of the matrix $P_{Y|X}$. Next, we subtract $q_1^{\ast }$ from the first row and reorder each column and update the matrix. We then choose the smallest number from the first row of the updated matrix and represent it by $q_2^{\ast }$. We continue this procedure until the summation of $q_i^{\ast }$ reaches one. To see an example, refer to ([36], Example 1).

Finally, we recall the two-part construction coding which was used in [1]. To do so, let us consider the scenario illustrated in Figure 1 where an encoder wishes to compress Y and communicates it to a user over an unsecured channel. The encoded message is described by the RV $\mathcal{C}$. As shown in Figure 1, it is assumed that an adversary has access to the encoded message $\mathcal{C}$, and wants to extract information about X. Moreover, it is assumed that the encoder and decoder have access to a shared secret key denoted by the RV W with size M. The goal is to design an encoded message $\mathcal{C}$, which compresses Y, using a variable length code with the minimum possible average length that satisfies a zero leakage constraint. The shared secret key is denoted by the discrete RV W defined on $\{1,\dots ,M\}$ and is assumed to be accessible by both the encoder and decoder. Furthermore, we assume that W is uniformly distributed and is independent of X and Y.

Theorem 3

([1], Theorem 8). Let $0\le ϵ\le H(X)$ and the pair of RVs $(X,Y)$ be distributed according to $P_{XY}$, and the shared secret key size be $|\mathcal{X}|$, i.e., $M=|\mathcal{X}|$. Then, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+1+\lceil log(|\mathcal{X}|)\rceil ,\end{array}$$

(25)

where $\alpha ={\displaystyle \frac{ϵ}{H(X)}}$ and if $|\mathcal{Y}|$ is finite, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le \lceil log\left(|\mathcal{X}|(|\mathcal{Y}|-1)+1\right)\rceil +\lceil log(|\mathcal{X}|)\rceil ,\hfill \end{array}$$

(26)

Finally, if X is a deterministic function of Y, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le \lceil log(\left(|\mathcal{Y}|-|\mathcal{X}|+1\right))\rceil +\lceil log(|\mathcal{X}|)\rceil .\hfill \end{array}$$

(27)

Proof. 

Let W be the shared secret key with key size $M=|\mathcal{X}|$, which is uniformly distributed over $\{1,\dots ,M\}=\{1,\dots ,|\mathcal{X}|\}$ and independent of $(X,Y)$. As shown in Figure 2, first, the private data X are encoded using the shared secret key. Thus, we have

$$\begin{array}{c}\hfill \tilde{X}=X+W\mathrm{mod}|\mathcal{X}|.\end{array}$$

Next, we show that $\tilde{X}$ has a uniform distribution over $\{1,\dots ,|\mathcal{X}|\}$ and $I(X;\tilde{X})=0$. We have

$$\begin{array}{c}\hfill H(\tilde{X}|X)=H(X+W|X)=H(W|X)=H(W)=log(|\mathcal{X}|).\end{array}$$

(28)

Furthermore, $H(\tilde{X}|X)\le H(\tilde{X})$, and combining it with (28), we obtain $H(\tilde{X}|X)=H(\tilde{X})=log(|\mathcal{X}|)$. For encoding $\tilde{X}$, we use $\lceil log(|\mathcal{X}|)\rceil$ bits. Let ${\mathcal{C}}_1$ denote the encoded $\tilde{X}$. Next, by using the construction in ([1], Lemma 2), let $U^{\ast }$ be the output of FRL. Thus, we have

$$\begin{array}{}\mathrm{(29)}& \hfill I(U^{\ast };X)& =0,\hfill \mathrm{(30)}& \hfill H(Y|U^{\ast },X)& =0,\hfill \mathrm{(31)}& \hfill H(U^{\ast })& \le \sum _{x}H(Y|X=x)+1.\hfill \end{array}$$

We encode $U^{\ast }$ using any lossless code which uses at most $H(U^{\ast })+1$ bits and let ${\mathcal{C}}_2$ be the encoded message $U^{\ast }$. We send $\mathcal{C}=({\mathcal{C}}_1,{\mathcal{C}}_2)$ over the channel. Thus, (25) can be obtained. Note that, as shown in Figure 3, on the decoder side, we first decode X using W, by adding $|\mathcal{X}|-W$ to $\tilde{X}$, then, Y is decoded using the fact that $U^{\ast }$ satisfies $H(Y|U^{\ast },X)=0$. Next, we show that if W is independent of $(X,U^{\ast })$ we obtain $I(\mathcal{C};X)=0$. We have

$$\begin{array}{cc}\hfill I(\mathcal{C};X)& =I({\mathcal{C}}_1,{\mathcal{C}}_2;X)=I(U,\tilde{X};X)\hfill \\ & =I(U^{\ast };X)+I(\tilde{X};X|U)=I(\tilde{X};X|U^{\ast })\hfill \\ & \stackrel{(a)}{=}H(\tilde{X}|U^{\ast })-H(\tilde{X}|X,U^{\ast })\hfill \\ & =H(\tilde{X}|U^{\ast })-H(X+W|X,U^{\ast })\hfill \\ & \stackrel{(b)}{=}H(\tilde{X}|U^{\ast })-H(W)\hfill \\ & \stackrel{(c)}{=}H(\tilde{X})-H(W)=log(|\mathcal{X}|)-log(|\mathcal{X}|)=0\hfill \end{array}$$

where (a) follows from $I(U^{\ast };X)=0$; (b) follows, since W is independent of $(X,U^{\ast })$; and (c) from the independence of $U^{\ast }$ and $\tilde{X}$. The latter follows, since we have

$$\begin{array}{cc}\hfill 0\le I(\tilde{X};X|U^{\ast })& =H(\tilde{X}|U^{\ast })-H(W)\hfill \\ & \stackrel{(i)}{=}H(\tilde{X}|U^{\ast })-H(\tilde{X})\le 0.\hfill \end{array}$$

Thus, $\tilde{X}$ and $U^{\ast }$ are independent. Step (i) above follows by the fact that W and $\tilde{X}$ are uniformly distributed over $\{1,\dots ,|\mathcal{X}|\}$, i.e., $H(W)=H(\tilde{X})$. As a summary, if we choose W independently of $(X,U^{\ast })$, the leakage to the adversary is zero.  □

4. Main Results

Here, we find upper and lower bounds on (5), (6) and (8), and study them in different scenarios.

4.1. Zero Leakage Results

In this section, we derive upper and lower bounds on ${\mathbb{L}}^0(P_{XY},M,ϵ)$ defined in (8). We first study the properties of ${\widehat{\mathcal{P}}}_{XY}$ and provide a sufficient condition on $P_{XY}$ so that it belongs to the corresponding set. We then find upper bounds on the entropy of the optimizers of $g_0(P_{XY})$ and $h_0(P_{XY})$. The obtained bounds help us to find upper bounds on ${\mathbb{L}}^0(P_{XY},M)$. In other words, for $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, we use the solutions of $g_0(P_{XY})$ and $h_0(P_{XY})$ to design $\mathcal{C}$; however, in [1], the design of the code was based on the functional representation lemma. Finally, we provide lower bounds on ${\mathbb{L}}^0(P_{XY},M)$, study the bounds in a numerical example, and compare them with [1].

In the next lemma, let $C(X,Y)$ denote the common information between X and Y, where the common information corresponds to the Wyner [44] or Gács-Körner [45] notions of common information.

Lemma 3.

If $C(X,Y)=I(X;Y)$, then $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$.

Proof. 

The proof is provided in ([18], Proposition 6) with $ϵ=0$ and follows similar arguments as the proof of ([46], Theorem 2).  □

Corollary 2.

If X is a deterministic function of Y, then $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, since, in this case, we have $C(X,Y)=I(X;Y)$. Furthermore, this result was also shown in ([18], Proposition 6).

In the next result, we provide the properties of the optimizers for $g_0(P_{XY})$ and $h_0(P_{XY})$.

Lemma 4.

If $g_0(P_{XY})=h_0(P_{XY})$, then

$$\begin{array}{c}\hfill g_0(P_{XY})=h_0(P_{XY})=H(Y|X),\end{array}$$

(32)

and both $g_0(P_{XY})$ and $h_0(P_{XY})$ have the same set of optimizers. Furthermore, for any optimizer $U^{\ast }$, we have

$$\begin{array}{}\mathrm{(33)}& \hfill H(Y|U^{\ast },X)=0,\mathrm{(34)}& \hfill I(X;U^{\ast }|Y)=0,\mathrm{(35)}& \hfill I(X;U^{\ast })=0.\end{array}$$

Finally, if U satisfies (33)–(35), then it is an optimizer for both $g_0(P_{XY})$ and $h_0(P_{XY})$.

Proof. 

All the statements can be shown using ([1], Theorem 7) and the key equation as follows:

$$\begin{array}{c}\hfill I(U;Y)=I(X;U)+H(Y|X)-I(X;U|Y)-H(Y|X,U).\end{array}$$

(36)

 □

Remark 6.

The optimization problems in (9) and (10) do not have unique optimizers. For instance, let $X=f(Y)$, by using the constructions used in [1,47], we can attain the optimum value.

Next, we show that if $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, without loss of optimality, we can assume that $|\mathcal{U}|\le \mathrm{null}(P_{X|Y})+1$, where $\mathrm{null}(P_{X|Y})$ corresponds to the dimension of the null space of $P_{X|Y}$.

Lemma 5.

For any $P_{XY}$, we have

$$\begin{array}{c}\hfill g_0(P_{XY})=\underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y}:X-Y-U,\\ I(X;U)=0,\\ |\mathcal{U}|\le \mathit{null}(P_{X|Y})+1\end{array}\end{array}}{max}I(Y;U).\end{array}$$

(37)

Furthermore, let $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$. Then,

$$\begin{array}{}& \hfill h_0(P_{XY})& =g_0(P_{XY})\hfill \mathrm{(38)}& & =\underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y}:X-Y-U\\ I(X;U)=0,\\ |\mathcal{U}|\le \mathit{null}(P_{X|Y})+1\end{array}\end{array}}{max}I(Y;U)\hfill \mathrm{(39)}& & =\underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y}:I(X;U)=0,\\ |\mathcal{U}|\le \mathit{null}(P_{X|Y})+1\end{array}\end{array}}{max}I(Y;U)\hfill \end{array}$$

Proof. 

The proof of (37) is provided in ([15], Theorem 1). It only remains to show the equality $(38)=(39)$. Let $U^{\ast }$ be an optimizer of (38). Using (37), it is also an optimizer of $g_0(P_{XY})$ and hence $h_0(P_{XY})$. Thus, $(38)=(39)$. In other words, for $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, we can assume $|\mathcal{U}|\le \mathrm{null}(P_{X|Y})+1$ in both problems $g_0(P_{XY})$ and $h_0(P_{XY})$.  □

Before stating the next result, let us define a set ${\mathcal{U}}^1(P_{XY})$ and a function $\mathcal{K}(P_{XY})$ as follows

$$\begin{array}{}\mathrm{(40)}& \hfill {\mathcal{U}}^1(P_{XY})& \triangleq \{U:U\mathrm{satisfies}(33),(34),(35)\}\hfill \mathrm{(41)}& \hfill \mathcal{K}(P_{XY})& \triangleq \underset{U\in {\mathcal{U}}^1(P_{XY})}{min}H(U).\hfill \end{array}$$

Note that ${\mathcal{U}}^1(P_{XY})$ can be empty for some joint distributions $P_{XY}$; however, using Lemma 4 when $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$ it is the set which contains all the optimizers satisfying $g_0(P_{XY})=h_0(P_{XY})$. Furthermore, the function $\mathcal{K}(P_{XY})$ finds the minimum entropy of all optimizers satisfying $g_0(P_{XY})=h_0(P_{XY})$.

Lemma 6.

Let $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$. We have

$$\begin{array}{c}\hfill \mathcal{K}(P_{XY})\le log(\mathit{null}(P_{X|Y})+1).\end{array}$$

(42)

Proof. 

The proof follows from Lemma 5. Let $U^{\ast }$ be any optimizer of $g_0(P_{XY})$ that satisfies $|{\mathcal{U}}^{\ast }|\le \mathrm{null}(P_{X|Y})+1$. We have $\mathcal{K}(P_{XY})\le H(U^{\ast })\le log(\mathrm{null}(P_{X|Y})+1)$.  □

Remark 7.

Lemma 6 asserts that when $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, there exist a U that satisfies (33)–(35), and

$$\begin{array}{c}\hfill H(U)\le log(\mathit{null}(P_{X|Y})+1).\end{array}$$

(43)

Remark 8.

The upper bound derived in Lemma 6 can be significantly smaller than the upper bound obtained in ([1], Lemma 2). This helps us to find codes that have a lesser average length compared to [1]. Noting that ([1], Lemma 2) asserts that there exists U which satisfies (33) and (35), and

$$\begin{array}{c}\hfill |\mathcal{U}|\le |\mathcal{X}|(|\mathcal{Y}|-1)+1,\end{array}$$

which results in

$$\begin{array}{c}\hfill H(U)\le log(|\mathcal{X}|(|\mathcal{Y}|-1)+1).\end{array}$$

(44)

In the next example, we compare (44) and (43).

Example 1.

Let Y be a deterministic function of X, i.e., $Y=f(X)$, which yields $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$ and $\mathcal{Y}\le |\mathcal{X}|$. In this case, $\mathit{null}(P_{X|Y})\le |\mathcal{X}|-1$. We have

$$\begin{array}{c}\hfill \mathit{null}(P_{X|Y})\le |\mathcal{X}|-1<|\mathcal{X}|(|\mathcal{Y}|-1),\end{array}$$

which results in

$$\begin{array}{c}\hfill (43)<(44).\end{array}$$

Furthermore, as $|\mathcal{X}|$ and $|\mathcal{Y}|$ grow, the gap between (33) and (34) becomes larger. To see another example, let X and Y be represented by $(X^{\prime },V)$ and $(Y^{\prime },V)$, where $X^{\prime }$ and $Y^{\prime }$ are conditionally independent given V, then by using [48], we have $I(X;Y)=C(X;Y)$ resulting in $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, where $C(X;Y)$ corresponds to the common information between X and Y. In this case, we have $\mathit{null}(P_{X|Y})\le max\{|\mathcal{X}|,|\mathcal{Y}|\}-1$. For $|\mathcal{X}|>2$, we have

$$\begin{array}{c}\hfill \mathit{null}(P_{X|Y})\le max\{|\mathcal{X}|,|\mathcal{Y}|\}-1<|\mathcal{X}|(|\mathcal{Y}|-1),\end{array}$$

which results in

$$\begin{array}{c}\hfill (43)<(44).\end{array}$$

Intuitively, when $|\mathcal{X}|$ and $|\mathcal{Y}|$ are large, (43) can be significantly less than (44), since $\mathit{null}(P_{X|Y})\le max\{|\mathcal{X}|,|\mathcal{Y}|\}-1$ and (44) includes multiplication of $|\mathcal{X}|$ and $|\mathcal{Y}|$.

Before stating the next result, we define

$$\begin{array}{}\mathrm{(45)}& \hfill A_{XY}& \triangleq \left[\begin{array}{cccc}& P_{y_1}-P_{y_1|x_1}& \dots & P_{y_q}-P_{y_q|x_1}\\ & ·& \dots & ·\\ & P_{y_1}-P_{y_1|x_t}& \dots & P_{y_q}-P_{y_q|x_t}\end{array}\right]\in {\mathbb{R}}^{t\times q},\hfill \mathrm{(46)}& \hfill b_{XY}& \triangleq \left[\begin{array}{c}H(Y|x_1)-H(Y|X)\\ ·\\ H(Y|x_t)-H(Y|X)\end{array}\right]\in {\mathbb{R}}^t,\mathit{a}\triangleq \left[\begin{array}{c}{a}_1\\ ·\\ a_q\end{array}\right]\in {\mathbb{R}}^q.\hfill \end{array}$$

where $t=|\mathcal{X}|$ and $q=|\mathcal{Y}|$.

Theorem 4.

Let $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$. For any $U\in {\mathcal{U}}^1$, we have

$$\begin{array}{}\mathrm{(47)}& \hfill H(Y|X)+\underset{a_i:A_{XY}\mathit{a}=b_{XY},\mathit{a}\ge 0}{min}\sum _{i=1}^q{P}_{y_i}{a}_i\le \mathcal{K}(P_{XY})\le \mathrm{(48)}& \hfill H(U)\le H(Y|X)+\underset{a_i:A_{XY}\mathit{a}=b_{XY},\mathit{a}\ge 0}{max}\sum _{i=1}^q{P}_{y_i}{a}_i.\end{array}$$

The upper bound can be strengthened and we have

$$\begin{array}{}\mathrm{(49)}& \hfill \mathcal{K}(P_{XY})& \le H(Y|X)+\underset{\begin{array}{c}\begin{array}{c}{a}_i:A_{XY}\mathit{a}=b_{XY},\mathit{a}\ge 0,\\ {\sum }_{i=1}^q{P}_{y_i}{a}_i\le log(\mathit{null}(P_{X|Y})+1)-H(Y|X)\end{array}\end{array}}{max}\sum _{i=1}^q{P}_{y_i}{a}_i\hfill \mathrm{(50)}& & \le log(\mathit{null}(P_{X|Y})+1).\hfill \end{array}$$

Moreover, when $\mathit{rank}(A_{XY})=|\mathcal{Y}|$ and $Y\ne f(X)$, we have $|{\mathcal{U}}^1|=1$, and for the unique optimizer we have

$$\begin{array}{c}\hfill \mathcal{K}(P_{XY})=H(Y|X)+\sum _i{P}_{y_i}{a}_i\end{array}$$

(51)

where $A_{XY}\mathit{a}=b_{XY},\mathit{a}\ge 0$ and ${\sum }_{i=1}^q{P}_{y_i}{a}_i\le log(\mathit{null}(P_{X|Y})+1)-H(Y|X)$.

Proof. 

The proof is provided in Appendix A.  □

Remark 9.

As we outlined earlier, it is shown in [15] that $g_0(P_{XY})$ can be obtained by a linear program which is presented in Section 3. As we can see in Section 3, each extreme point ${\alpha }_i$ is a vector with size $|\mathcal{Y}|$ in which at most $\mathit{rank}(P_{X|Y})$ elements are non-zero. We recall that β corresponds to the weighting elements in the marginal distribution of U, i.e., $\beta =P_U$. The number of extreme points is at most $\left({\displaystyle \genfrac{}{}{0pt}{}{|\mathcal{Y}|}{\mathit{rank}(P_{X|Y})}}\right)$. Hence, if we consider the linear equations $[{\alpha }_1{\alpha }_2\dots {\alpha }_K]\beta =P_Y$, the size of the matrix in the system of linear equations, i.e., $[{\alpha }_1{\alpha }_2\dots {\alpha }_K]$, is at most $|\mathcal{Y}|\times \left({\displaystyle \genfrac{}{}{0pt}{}{|\mathcal{Y}|}{\mathit{rank}(P_{X|Y})}}\right)$ and we have at most $\left({\displaystyle \genfrac{}{}{0pt}{}{|\mathcal{Y}|}{\mathit{rank}(P_{X|Y})}}\right)$ variables in the system. By solving the linear program proposed in [15] we can find the exact value of $\mathcal{K}(P_{XY})$ and the conditional distribution $P_{U|YX}$ that attains it. The complexity of the linear program in [15] can grow faster than the exponential functions with respect to $|\mathcal{Y}|$; however, the complexity of our proposed method grows linearly with $|\mathcal{Y}|$. The latter follows since, by considering the system of linear equations in our proposed method $A_{XY}\mathit{a}=b_{XY}$, the size of matrix is $|\mathcal{X}|\times |\mathcal{Y}|$ and we do not need to find all possible extreme points of the set $\mathcal{S}$ presented in Section 3. Thus, our proposed upper bound has less complexity compared to the solution in [15]. Furthermore, in a special case where $\mathit{rank}(A_{XY})=|\mathcal{Y}|$, we can find the exact value of $\mathcal{K}(P_{XY})$ using our method. One necessary condition for $\mathit{rank}(A_{XY})=|\mathcal{Y}|$ is to have $|\mathcal{X}|\ge |\mathcal{Y}|+1$, since the summation of rows in $A_{XY}$ equals zero.

Remark 10.

The optimizer of $g_0(P_{XY})$ does not help us to build $\mathcal{C}$, since the constraint $H(Y|U,X)=0$ does not hold in general; however, the optimizer of $h_0(P_{XY})$ satisfies it. Hence, we consider the cases where the equality $g_0(P_{XY})=h_0(P_{XY})$ holds. In this case, $H(Y|U,X)=0$ and we have tighter bounds on $H(U)$ compared to [1].

Remark 11.

The upper bound in (48) holds for any $U\in {\mathcal{U}}^1$; however, the upper bound in (48) asserts that there exists $U\in {\mathcal{U}}^1$ such that the bound holds. The lower bound in (47) can be used to find a lower bound on ${\mathbb{L}}^0(P_{XY},M)$. Similarly to Remark 9, the linear program attaining the lower bound in (47) has less complexity than [15].

Next, we obtain upper and lower bounds on ${\mathbb{L}}^0(P_{XY},M)$. See Figure 4 and Figure 5.

Theorem 5.

For the pair of RVs $(X,Y)$, let $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$ and the shared secret key size be $|\mathcal{X}|$, i.e., $M=|\mathcal{X}|$. Furthermore, let $q=|\mathcal{Y}|$ and $\beta =log(\mathit{null}(P_{X|Y})+1)$. Then, we obtain

$$\begin{array}{}\mathrm{(52)}& {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le \mathcal{K}(P_{XY})+1+\lceil log(|\mathcal{X}|)\rceil \hfill \mathrm{(53)}& \le H(Y|X)+\underset{\begin{array}{c}\begin{array}{c}{a}_i:A_{XY}\mathit{a}=b_{XY},\mathit{a}\ge 0,\\ {\sum }_{i=1}^q{P}_{y_i}{a}_i\le \beta -H(Y|X)\end{array}\end{array}}{max}\sum _{i=1}^q{P}_{y_i}{a}_i+1+\lceil log(|\mathcal{X}|)\rceil \hfill \mathrm{(54)}& \le \beta +1+\lceil log(|\mathcal{X}|)\rceil \hfill \end{array}$$

For any $P_{XY}$, we have

$$\begin{array}{}\mathrm{(55)}& {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le \underset{\begin{array}{c}\begin{array}{c}{P}_{U|Y,X}:I(U;X)=0,\\ H(Y|X,U)=0\end{array}\end{array}}{min}H(U)+1+\lceil log(|\mathcal{X}|)\rceil \hfill \mathrm{(56)}& \le 1+min(\sum _{x}H(Y|X=x),log(|\mathcal{X}|(|\mathcal{Y}|-1)+1)-1)+\lceil log(|\mathcal{X}|)\rceil ,\hfill \end{array}$$

and if $X=f(Y)$,

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le \lceil log(|\mathcal{Y}|-|\mathcal{X}|+1)\rceil +\lceil log(|\mathcal{X}|)\rceil .\end{array}$$

(57)

Finally, for any $P_{XY}$ with $|\mathcal{Y}|\le |\mathcal{X}|$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},|\mathcal{Y}|)\le \lceil log|\mathcal{Y}|\rceil .\end{array}$$

(58)

Proof. 

All upper bounds can be obtained using two-part construction coding [1] and the complete proof is provided in Appendix A.  □

Next, we obtain lower bounds on ${\mathbb{L}}^0(P_{XY},M)$.

Theorem 6.

For any pair of RVs $(X,Y)$ distributed according to $P_{XY}$ and shared key size $M\ge 1$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},M)\ge \underset{x}{max}H(Y|X=x),\end{array}$$

(59)

if $X=f(Y)$,

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\ge log(|\mathcal{X}|),\end{array}$$

(60)

and the code $\mathcal{C}$ does not exist when $M<|\mathcal{X}|$ and $X=f(Y)$. Furthermore, considering $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, if we assume the received code $\mathcal{C}$ satisfies $I(X;\mathcal{C})=0$, $H(Y|X,\mathcal{C})=0$ and $X-Y-\mathcal{C}$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},M)\ge H(Y|X)+\underset{a_i:A_{XY}\mathit{a}=b_{XY},\mathit{a}\ge 0}{min}\sum _{i=1}^q{P}_{y_i}{a}_i.\end{array}$$

(61)

Proof. 

The proofs of (59) and (60) are provided in ([1], Theorem 9) and (61) follows from Theorem 4.  □

Remark 12.

The constraint $X-Y-\mathcal{C}$ in the converse bound (61) can be motivated by considering the cases where the encoder has no direct access to the private data X. Furthermore, the constraint $H(Y|X,\mathcal{C})=0$ is stronger compared to the $H(Y|X,\mathcal{C},W)=0$ that is used to prove (59). Specifically, the constraint needed to prove (59) is $H(Y|\mathcal{C},W)=0$, which results in $H(Y|X,\mathcal{C},W)=0$.

4.2. Comparison

In this part, we study the bounds obtained in Theorem 5 and compare them with the existing results in [1].

• Case 1: $|\mathcal{Y}|\le |\mathcal{X}|$

Clearly, for any $P_{XY}$ with $|\mathcal{Y}|\le |\mathcal{X}|$, the upper bound obtained in (58) improves the bounds in (56) and (55), where (56) was derived in [1]. The latter follows, since in this case we have $\lceil log(|\mathcal{Y}|)\rceil \le \lceil log(|\mathcal{X}|)\rceil$.

• Case 2: $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$

In this part, let $X=f(Y)$, which results in $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$, see Corollary 1. The upper bound attained by [1] is $\lceil log(|\mathcal{Y}|-|\mathcal{X}|+1)\rceil +\lceil log(|\mathcal{X}|)\rceil$. Furthermore, we can assume that all elements in the probability vector $P_X$ are non-zero, otherwise we can remove them. the In this case, we have

$$\begin{array}{c}\hfill \mathrm{null}(P_{X|Y})=|\mathcal{Y}|-|\mathcal{X}|.\end{array}$$

(62)

This follows, since each column in $P_{X|Y}$ contains exactly one non-zero element that equals 1. Moreover, all rows of $P_{X|Y}$ are linearly independent, since each row contains a non-zero element that the other rows do not have. Thus, $\mathrm{rank}(P_{X|Y})=|\mathcal{X}|$, which results $\mathrm{null}(P_{X|Y})=|\mathcal{Y}|-|\mathcal{X}|$. Thus, the upper bound in (54) can be modified to obtain the same bound as (57). Furthermore, the upper bounds (53) and (52) attain less quantities compared to (57), i.e., they can improve the bounds in [1]. Next, in a numerical example, we show that the upper bounds (53) and (52) improve (57).

Example 2.

Let $P_{X|Y}=\left[\begin{array}{cccccc}1& 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 1\end{array}\right]$ and $P_Y=[{\displaystyle \frac{1}{8}},{\displaystyle \frac{2}{8}},{\displaystyle \frac{3}{8}},{\displaystyle \frac{1}{8}},{\displaystyle \frac{1}{16}},{\displaystyle \frac{1}{16}}]$. Clearly, in this case X is a deterministic function of Y. Using the linear program proposed in [15], we obtain a solution as $P_{Y|u_1}=[0.75,0,0,0.25,0,0]$, $P_{Y|u_2}=[0,0.75,0,0.25,0,0]$, $P_{Y|u_3}=[0,0,0.75,0,0.25,0]$, $P_{Y|u_4}=[0,0,0.75,0,0,0.25]$ and $P_U=[{\displaystyle \frac{1}{6}},{\displaystyle \frac{1}{3}},{\displaystyle \frac{1}{4}},{\displaystyle \frac{1}{4}}]$, which results in $H(U)=1.9591$ bits. We have $\mathcal{K}(P_{XY})+1\le 2.9591$ and $\lceil log(|\mathcal{Y}|-|\mathcal{X}|+1)\rceil =\lceil log5\rceil =3$. Hence, the upper bound (52) is strictly lower than (57), i.e., the $U^{\ast }$ that achieves $g_0(P_{XY})$ has less entropy than the RV U constructed in ([1], Lemma 1).

4.3. Improving the Bounds Using Greedy Entropy-Based Algorithm

In this part, we use the greedy entropy-based algorithm to generalize the bounds obtained in Theorem 5. In more detail, we use the output of the greedy entropy-based algorithm in Theorem 1 instead of the solution to $g_0(P_{XY})=h_0(P_{XY})$. In the next theorem, let $Q^{\ast }=(q_1^{\ast },q_2^{\ast },\dots )$ with $q_1^{\ast }\ge q_2^{\ast }\ge \dots$, where $q_i=P(Q=q_i)$. Let $P_{Y|X}$ be a matrix with columns $P_{Y|X=x}$, and we re-order each column so that each column has a descending order. Let $q_1^{\ast }={min}_{x\in \mathcal{X}}\left\{{max}_{y\in \mathcal{Y}}{P}_{Y|X}(y|x)\right\}$, i.e., choose the smallest number in the first row of the matrix $P_{Y|X}$, and then we subtract $q_1^{\ast }$ from the first row and reorder each column and update the matrix. We then choose the smallest number from the first row of the updated matrix and represent it by $q_2^{\ast }$. We continue this procedure until the summation of $q_i^{\ast }$ reaches one.

Theorem 7.

Let the RVs $(X,Y)$ be distributed according to $P_{XY}$ supported on alphabets $\mathcal{X}$ and $\mathcal{Y}$, where $|\mathcal{X}|$ and $|\mathcal{Y}|$ are finite, and let the shared secret key size be $|\mathcal{X}|$, i.e., $T=|\mathcal{X}|$. Let $|X|=2$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},2)\le H(Q^{\ast })+{\displaystyle \frac{loge}{e}}+2,\end{array}$$

(63)

where $Q^{\ast }$ is defined in ([36], Lemma 3). When $|X|>2$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^0(P_{XY},|\mathcal{X}|)\le H(Q^{\ast })+{\displaystyle \frac{1+loge}{2}}+1+\lceil log(|\mathcal{X}|)\rceil ,\end{array}$$

(64)

Proof. 

The proof is similar to Theorem 5 and the main difference is to use the minimum entropy output of (19) instead of the solution to $g_0(P_{XY})=h_0(P_{XY})$ that is used in two-part construction coding. Similarly to Theorem 5, we use two-part code construction to achieve the upper bounds. As shown in Figure 6, we first encode the private data X using one-time pad coding ([2], Lemma 1), which uses $\lceil log(|\mathcal{X}|)\rceil$ bits. Next, we produce U based on the greedy entropy-based algorithm proposed in [34], which solves the minimum entropy problem in (19). Thus, we have

$$\begin{array}{}\mathrm{(65)}& \hfill H(Y|X,U)=0,\mathrm{(66)}& \hfill I(U;X)=0,\end{array}$$

and

$$\begin{array}{c}\hfill H(U)\le H(Q^{\ast })+{\displaystyle \frac{loge}{e}},\end{array}$$

(67)

and for $|X|>2$,

$$\begin{array}{c}\hfill H(U)\le H(Q^{\ast })+{\displaystyle \frac{1+loge}{2}}.\end{array}$$

(68)

Thus, we obtain (63) and (64). Moreover, for the leakage constraint, we note that the randomness of one-time-pad coding is independent of X and the output of the greedy entropy-based algorithm U.

On the user side, we can decode Y using (65).  □

Remark 13.

We emphasize that (63) and (64) can improve (52), since they achieve the minimum in (56) within a gap, i.e., achieve ${min}_{\begin{array}{c}\begin{array}{c}{P}_{U|Y,X}:I(U;X)=0,\\ H(Y|X,U)=0\end{array}\end{array}}H(U)$ up to a constant gap that depends on $|\mathcal{X}|$. Furthermore, in contrast with the bounds in Theorem 5, (63) and (64) can be achieved for any joint distribution $P_{XY}$. However, in the following numerical example, we show that the bounds in Theorem 5 can be tighter than those in Theorem 7.

Example 3.

Let $P_{X|Y}=\left[\begin{array}{cccccc}1& 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 1\end{array}\right]$ and $P_Y=[{\displaystyle \frac{1}{8}},{\displaystyle \frac{2}{8}},{\displaystyle \frac{3}{8}},{\displaystyle \frac{1}{8}},{\displaystyle \frac{1}{16}},{\displaystyle \frac{1}{16}}]$. Clearly, in this case, X is a deterministic function of Y. Using the linear program proposed in [15], we obtain a solution as $P_{Y|u_1}=[0.75,0,0,0.25,0,0]$, $P_{Y|u_2}=[0,0.75,0,0.25,0,0]$, $P_{Y|u_3}=[0,0,0.75,0,0.25,0]$, $P_{Y|u_4}=[0,0,0.75,0,0,0.25]$ and $P_U=[{\displaystyle \frac{1}{6}},{\displaystyle \frac{1}{3}},{\displaystyle \frac{1}{4}},{\displaystyle \frac{1}{4}}]$ which results $H(U)=1.9591$ bits. We have $H(U)=\mathcal{K}(P_{XY})\le 1.9591$. Moreover, we have

$$\begin{array}{c}\hfill P_{Y|X}=\left[\begin{array}{cc}{\displaystyle \frac{1}{6}}& 0\\ {\displaystyle \frac{1}{3}}& 0\\ {\displaystyle \frac{1}{2}}& 0\\ 0& {\displaystyle \frac{1}{2}}\\ 0& {\displaystyle \frac{1}{4}}\\ 0& {\displaystyle \frac{1}{4}}\end{array}\right].\end{array}$$

Using the greedy search algorithm, we have $P_{Q\ast }=\left[{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{4}}{\displaystyle \frac{1}{6}}{\displaystyle \frac{1}{12}}\right]$, hence, $H(Q^{\ast })=1.7296$. Thus,

$$\begin{array}{c}\hfill H(Q^{\ast })+{\displaystyle \frac{loge}{e}}=2.2596\ge \mathcal{K}(P_{XY})=1.9591.\end{array}$$

In the next example, we show that the bounds in Theorem 7 can be tighter than the bounds obtained in Theorem 5.

Example 4.

Let $P_{X|Y}=\left[\begin{array}{cccccc}1& 1& 0& 0& 0& 0\\ 0& 0& 1& 1& 1& 1\end{array}\right]$ and $P_Y=[{\displaystyle \frac{1}{8}},{\displaystyle \frac{2}{8}},{\displaystyle \frac{3}{8}},{\displaystyle \frac{1}{8}},0.0925,0.0325]$. Similarly to the previous example, X is a deterministic function of Y. Using the linear program proposed in [15], we obtain a solution as $P_U=[0.185,0.065,0.315,0.25,0.185]$, which results in $H(U)=2.1696$ bits. We have $H(U)=\mathcal{K}(P_{XY})=2.182$. Moreover, we have

$$\begin{array}{c}\hfill P_{Y|X}=\left[\begin{array}{cc}{\displaystyle \frac{1}{3}}& 0\\ {\displaystyle \frac{2}{3}}& 0\\ 0& 0.6\\ 0& 0.2\\ 0& 0.148\\ 0& 0.052\end{array}\right].\end{array}$$

Using the greedy search algorithm, we have $P_{Q\ast }=\left[0.60.20.13330.0520.0147\right]$, hence, $H(Q^{\ast })=1.6053$. Thus,

$$\begin{array}{c}\hfill H(Q^{\ast })+{\displaystyle \frac{loge}{e}}=2.136\le \mathcal{K}(P_{XY})=2.182.\end{array}$$

4.4. Non-Zero Leakage Results

In this section, we derive upper and lower bounds on $\mathbb{L}(P_{XY},M,ϵ)$ and ${\mathbb{L}}^b(P_{XY},M,ϵ)$, defined in (5) and (6). Next, we study the bounds in different scenarios; moreover, we provide an example that shows that the bounds can be tight. The following lemma helps us to find lower bounds on the entropy of an RV that satisfies $I(U;X)=ϵ$ and $H(Y|U,X)=0$ considering the shared key.

Lemma 7.

Let the pair $(X,Y)$ be jointly distributed and the RV W be independent of X and Y. Then, if the RV U satisfies $I(U;X)=ϵ,$ and $H(Y|U,X,W)=0,$ then, we have

$$\begin{array}{c}\hfill H(U)\ge max\{L_1(ϵ,P_{XY}),L_2(ϵ,P_{XY}),L_3(ϵ,P_{XY})\},\end{array}$$

(69)

where

$$\begin{array}{}\mathrm{(70)}& L_1(ϵ,P_{XY})=H(Y|X),\hfill \mathrm{(71)}& L_2(ϵ,P_{XY})=\underset{x\in \mathcal{X}}{min}H(Y|X)+ϵ,\hfill \mathrm{(72)}& L_3(ϵ,P_{XY})=H(Y|X)-H(X|Y)+ϵ,\hfill \end{array}$$

and ${min}_{x\in \mathcal{X}}H(Y|X=x)$ is the minimum conditional entropy which is non-zero.

Proof. 

The proof is provided in Appendix B.  □

In the next two theorems, we provide upper and lower bounds on $\mathbb{L}(P_{XY},M,ϵ)$. The next theorem is a generalization of ([1], Theorem 8) for correlated $\mathcal{C}$ and X.

Theorem 8.

Let $0\le ϵ\le H(X)$ and the pair of RVs $(X,Y)$ be distributed according to $P_{XY}$, and the shared secret key size be $|\mathcal{X}|$, i.e., $M=|\mathcal{X}|$. Then, we have

$$\begin{array}{cc}\hfill \mathbb{L}(P_{XY},|\mathcal{X}|,ϵ)& \le \sum _{x\in \mathcal{X}}H(Y|X=x)+ϵ+h(\alpha )+1+\lceil log(|\mathcal{X}|)\rceil ,\hfill \end{array}$$

(73)

where $\alpha ={\displaystyle \frac{ϵ}{H(X)}}$ and if $|\mathcal{Y}|$ is finite, we have

$$\begin{array}{cc}\hfill & \mathbb{L}(P_{XY},|\mathcal{X}|,ϵ)\le \lceil log\left(|\mathcal{X}|(|\mathcal{Y}|-1)+1\right)\left(|\mathcal{X}|+1\right)\rceil +\lceil log(|\mathcal{X}|)\rceil ,\hfill \end{array}$$

(74)

Finally, if X is a deterministic function of Y, we have

$$\begin{array}{cc}\hfill & \mathbb{L}(P_{XY},|\mathcal{X}|,ϵ)\le \lceil log(\left(|\mathcal{Y}|-|\mathcal{X}|+1\right)\left[|\mathcal{X}|+1\right])\rceil +\lceil log(|\mathcal{X}|)\rceil .\hfill \end{array}$$

(75)

Proof. 

The proof is based on ([19], Lemma 5) and the two-part construction coding and is provided in Appendix B.  □

In the next theorem, we provide lower bounds on $\mathbb{L}(P_{XY},M,ϵ)$.

Theorem 9.

Let $0\le ϵ\le H(X)$ and the pair of RVs $(X,Y)$ be distributed according to $P_{XY}$ supported on alphabets $\mathcal{X}$ and $\mathcal{Y}$, where $|\mathcal{X}|$ is finite and $|\mathcal{Y}|$ is finite or countably infinite. For any shared secret key size $M\ge 1$, we have

$$\begin{array}{cc}\hfill & \mathbb{L}(P_{XY},M,ϵ)\ge max\{L_1(ϵ,P_{XY}),L_2(ϵ,P_{XY}),L_3(ϵ,P_{XY})\},\hfill \end{array}$$

(76)

where $L_1(ϵ,P_{XY})$, $L_2(ϵ,P_{XY})$ and $L_3(ϵ,P_{XY})$ are defined in (70), (71) and (72). Furthermore, if X is deterministic function of Y, then, we have

$$\begin{array}{c}\hfill \mathbb{L}(P_{XY},M,ϵ)\ge log({\displaystyle \frac{1}{{max}_x{P}_X(x)}}).\end{array}$$

(77)

Proof. 

The proof is based on Lemma 7 and is provided in Appendix B.  □

Next, we provide an example where the upper and lower bounds obtained in Theorems 8 and 9 are studied.

Example 5.

Let $Y=(Y_1,\dots ,Y_N)$ be an i.i.d Bernoulli($0.5$) sequence and $X_N={\displaystyle \frac{1}{N}}{\sum }_{i=1}^N{Y}_i$. Clearly, $X_N$ is a function of Y, $|\mathcal{X}|=N+1$ and $|\mathcal{Y}|=2^N$. Using ([1], (72)), we have

$$\begin{array}{c}\hfill h_0(P_{XY})\stackrel{(a)}{=}H(Y|X)=\sum _{i=1}^N{({\displaystyle \frac{1}{2}})}^N\left({\displaystyle \genfrac{}{}{0pt}{}{N}{i}}\right),\end{array}$$

(78)

where (a) follows from ([1], (70)). Let the shared key size be $N+1$, by using Theorems 8 and 9, we have

$$\begin{array}{cc}\hfill ϵ+\sum _{i=1}^N{({\displaystyle \frac{1}{2}})}^N\left({\displaystyle \genfrac{}{}{0pt}{}{N}{i}}\right)& \le \mathbb{L}(P_{XY},N+1,ϵ)\hfill \\ & \le log((N+2)(2^N-N))+log(N+1),\hfill \end{array}$$

(79)

where (75) is used for the upper bound and $L_3(ϵ,P_{XY})$ is used for the lower bound. Using ([1], (73)), we have

$$\begin{array}{c}\hfill \underset{N\to \infty }{lim}{\displaystyle \frac{h_0(P_{XY})}{N}}=\underset{N\to \infty }{lim}{\displaystyle \frac{H(Y|X)}{N}}=h(0.5)=1,\end{array}$$

(80)

where $h(·)$ is the binary entropy function. Now, by using (79) and (80), we obtain

$$\begin{array}{c}\hfill \underset{N\to \infty }{lim}{\displaystyle \frac{\mathbb{L}(P_{XY},N+1,ϵ)}{N}}=1\end{array}$$

(81)

• Bounds for Bounded Leakage Constraint

Here, we assume that $X=(X_1,X_2)$, where $\mathcal{X}={\mathcal{X}}_1\times {\mathcal{X}}_2$, $1<|{\mathcal{X}}_1|\le |{\mathcal{X}}_2|$, and $|{\mathcal{X}}_1||{\mathcal{X}}_2|=|\mathcal{X}|$. In the next theorem, we provide upper bounds for ${\mathbb{L}}^b(P_{XY},M,ϵ)$. We show that when the leakage is more than a threshold, we are able to communicate the message over the channel using a shared key size less than $|\mathcal{X}|$ and the receiver can decode the message without any loss.

Theorem 10.

Let $ϵ\ge H(X_1)$ and the RVs $(X_1,X_2,Y)$ be distributed according to $P_{X_1{X}_{2}Y}$ and let the shared secret key size be $|{\mathcal{X}}_2|$, i.e., $M=|{\mathcal{X}}_2|$. Then, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_2|,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+H(X_1)+2+\lceil log(|{\mathcal{X}}_2|)\rceil ,\hfill \end{array}$$

(82)

if $|\mathcal{Y}|$ is finite, then

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_2|,ϵ)\le \lceil log\left(|\mathcal{X}|(|\mathcal{Y}|-1)+1\right)\rceil +\lceil log(|{\mathcal{X}}_2|)\rceil +2+H(X_1),\hfill \end{array}$$

(83)

and if $X=(X_1,X_2)$ is deterministic function of Y, we obtain

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_2|,ϵ)\le \lceil log\left(|\mathcal{Y}|-|\mathcal{X}|+1\right)\rceil +\lceil log(|{\mathcal{X}}_2|)\rceil +2+H(X_1),\hfill \end{array}$$

(84)

Furthermore, let $ϵ\ge H(X_2)$ and the shared secret key size be $|{\mathcal{X}}_1|$. We have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_1|,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+H(X_2)+2+\lceil log(|{\mathcal{X}}_1|)\rceil ,\hfill \end{array}$$

(85)

Proof. 

The proof is similar to the proof of Theorem 8 and is provided in Appendix B.  □

Remark 14.

As argued in ([1], Theorem 9), when the leakage is zero and X is a deterministic function of Y, if the shared key size is less than the size of X, i.e., $M\le |\mathcal{X}|$, lossless variable-length codes do not exist. However, as is shown in Theorem 10, when the leakage is more than a threshold, for the key size less than $|\mathcal{X}|$, such codes exist.

Remark 15.

The upper bounds (82) and (85) can be less than the upper bound found in ([1], Theorem 9), which is obtained under perfect privacy assumption. For instance, if $H(X_1)+2\le log(|{\mathcal{X}}_1|)$, then (82) is less than ([1], (95)). The latter follows, since we have $H(X_1)+1+\lceil log(|{\mathcal{X}}_2|)\rceil \le log(|{\mathcal{X}}_1|)+\lceil log(|\mathcal{X}|)-log(|{\mathcal{X}}_1|)\rceil -1\le \lceil log(|{\mathcal{X}}_1|)\rceil +\lceil log(|\mathcal{X}|)-log(|{\mathcal{X}}_1|)\rceil -1\le \lceil log(|\mathcal{X}|)\rceil ,$ where the last inequality follows by $\lceil a\rceil +\lceil b\rceil \le \lceil a+b\rceil +1$.

In the next theorem, we find lower bounds for ${\mathbb{L}}^b(P_{XY},M,ϵ)$.

Theorem 11.

Let $0\le ϵ\le H(X)$ and the RVs $(X_1,X_2,Y)$ be distributed according to $P_{X_1{X}_{2}Y}$. For any shared secret key size $M\ge 1$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^b(P_{XY},M,ϵ)\ge H(Y|X)-H(X|Y).\end{array}$$

(86)

Furthermore, if X is a deterministic function of Y, then we have

$$\begin{array}{c}\hfill {\mathbb{L}}^b(P_{XY},M,ϵ)\ge log({\displaystyle \frac{1}{{max}_x{P}_X(x)}}).\end{array}$$

(87)

Proof. 

The proof is provided in Appendix B.  □

• A General Approach for X

Next, by using the same construction as in Theorem 10, we find upper bounds on ${\mathbb{L}}^b(P_{XY},M,ϵ)$ for any joint distribution $P_{XY}$. Next, we present a simple observation, which we call the separation technique.

Observation 1.

(Separation technique) Any discrete RV X supported on $\mathcal{X}=\{1,\dots ,|\mathcal{X}|\}$ with $|\mathcal{X}|>2$ can be represented by two RVs $(X_1,X_2)$, where $1<|{\mathcal{X}}_1|<|\mathcal{X}|$ and $1<|{\mathcal{X}}_2|<|\mathcal{X}|$.

If $|\mathcal{X}|$ is not a prime number, then we can show X by $(X_1,X_2)$ where $\mathcal{X}={\mathcal{X}}_1\times {\mathcal{X}}_2$, $1<|{\mathcal{X}}_1|\le |{\mathcal{X}}_2|$, $|{\mathcal{X}}_1||{\mathcal{X}}_2|=|\mathcal{X}|$ and $P_X(x)=P_{X_1,X_2}(x_1,x_2)$. Furthermore, if $|\mathcal{X}|$ is a prime number, then we can show X by $(X_1,X_2)$, where $|{\mathcal{X}}_1||{\mathcal{X}}_2|=|\mathcal{X}|+1$ and $P_{X_1,X_2}(|{\mathcal{X}}_1|,|{\mathcal{X}}_2|)=0$. Let ${\mathcal{S}}_X$ be all possible representations of X, where $X=(X_1,X_2)$. For a fixed $ϵ$, we define ${\mathcal{S}}_X^{1ϵ}\triangleq \{(X_1,X_2):(X_1,X_2)\in {\mathcal{S}}_X,H(X_1)\le ϵ\}$ and ${\mathcal{S}}_X^{2ϵ}\triangleq \{(X_1,X_2):(X_1,X_2)\in {\mathcal{S}}_X,H(X_2)\le ϵ\}$.

Theorem 12.

For any $ϵ\ge 0$, pair of RVs $(X,Y)$ distributed according to $P_{XY}$, and shared key size $M\ge \alpha$, if ${\mathcal{S}}_X^{1ϵ}\ne$, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},M,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+2+\underset{(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}}{min}\left\{H(X_1)+\lceil log(|{\mathcal{X}}_2|)\rceil \right\},\hfill \end{array}$$

(88)

where $\alpha =|{arg\; min}_{X_2:(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}}H(X_1)+\lceil log(|{\mathcal{X}}_2|)\rceil |<|\mathcal{X}|$ and $|S|$ denotes the size of the RV S. If ${\mathcal{S}}_X^{2ϵ}\ne$, for a shared key size $M\ge \beta$, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},M,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+2+\underset{(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}}{min}\left\{H(X_2)+\lceil log(|{\mathcal{X}}_1|)\rceil \right\},\hfill \end{array}$$

(89)

where $\alpha =|{arg\; min}_{X_1:(X_1,X_2)\in {\mathcal{S}}_X^{2ϵ}}H(X_1)+\lceil log(|{\mathcal{X}}_2|)\rceil |<|\mathcal{X}|$.

Proof. 

To prove (88), let $(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}$. Then, by using Theorem 10, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_2|,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+H(X_1)+2+\lceil log(|{\mathcal{X}}_2|)\rceil .\hfill \end{array}$$

(90)

Since (90) holds for any $(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}$, we can take the minimum over $(X_1,X_2)$, which results in (88). Furthermore, the key size is chosen as $|{arg\; min}_{X_2:(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}}H(X_1)+\lceil log(|{\mathcal{X}}_2|)\rceil |<|\mathcal{X}|$ and note that the first term ${\sum }_{x\in \mathcal{X}}H(Y|X=x)$ remains the same, since it is a function of $P_{Y|X_1{X}_2}$, i.e., the distributions including the pair $(X_1,X_2)$ do not change, since $P_{X_1,X_2}(x_1,x_2)=P_X(x)$. Using (85) and following the same approach, (89) is obtained.  □

Remark 16.

The upper bounds (88) and (89) generalize (82) and (85). The upper bounds (82) and (85) are obtained for a fixed $(X_1,X_2)$. Thus, by taking the minimum over $(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}$ and $(X_1,X_2)\in {\mathcal{S}}_X^{2ϵ}$, we obtain tighter upper bounds.

Remark 17.

The same lower bounds as obtained in Theorem 11 can be used here, since the separation technique does not improve the bounds in (86) and (87).

Remark 18.

Using Example 5, we can see that the bounds obtained in Theorems 10–13 can be asymptotically tight.

Next, we provide an example to clarify the construction in Theorem 12 and compare the bounds with the perfect privacy case.

Example 6.

Let the RV $X\in \{1,\dots ,12\}$ with distribution $P_X(x)=0.05,x\in \{1,\dots ,10\}$ and $P_X(x)=0.475,x\in \{11,12\}$ be correlated with Y, where $Y|X=x$ is a $\mathrm{BSC}(0.5)$. To calculate the bound in Theorem 12, one possible separation of X is $(X_1,X_2)$, where the distributions of $X_1$ and $X_2$ are $P_{X_1}(x_1)=0.01,x\in \{1,\dots ,5\}$, $P_{X_1}(x_1)=0.95,x_1=6$ and $P_{X_2}(x_2)=0.5,x\in \{1,2\}$. In this case, $H(X_1)=0.4025$ and $log(|{\mathcal{X}}_2|)=1$. Using the bound (82), for all $ϵ\ge 0.4025$ and key size $M\ge 1$, we have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},M,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+H(X_1)+2+\lceil log(|{\mathcal{X}}_2|)\rceil =15.45\mathrm{bits},\hfill \end{array}$$

By using the bound ([1], (95)), for the key size $M\ge 12$, we have

$$\begin{array}{c}\hfill {\mathbb{L}}^b(P_{XY},M,0)\le 17\mathrm{bits}.\end{array}$$

Note that, since $|\mathcal{Y}|=2$, we can also use the following bound instead of (88)

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},M,ϵ)\le \lceil log\left(|\mathcal{X}|(|\mathcal{Y}|-1)+1\right)\rceil +2\hfill \\ & +\underset{(X_1,X_2)\in {\mathcal{S}}_X^{1ϵ}}{min}\left\{\lceil log(|{\mathcal{X}}_2|)\rceil +H(X_1)\right\}.\hfill \end{array}$$

By checking all possible separations, the minimum of $\lceil log(|{\mathcal{X}}_2|)\rceil +H(X_1)$ occurs at $|{\mathcal{X}}_1|=6$, and $|{\mathcal{X}}_2|=2$ where $X_1$ and $X_2$ have the distributions mentioned before. Thus, for all $ϵ\ge 0.4025$ and the key size $M\ge 1$, we have ${\mathbb{L}}^b(P_{XY},M,ϵ)\le 7.4025\mathrm{bits}.$ By using the bound ([1], (96)), for the key size $M\ge 12$, we have ${\mathbb{L}}^b(P_{XY},M,0)\le 9\mathrm{bits}.$ We can see that by allowing a small amount of leakage with a shorter secret key size, we are able to send shorter codewords.

In the following, we study the bounds obtained in Theorem 12 considering a perfect privacy scenario and we show that the previous bounds can be improved by using the separation technique.

• Perfect Privacy ($ϵ=0$)

In this part, we let $ϵ=0$ and consider the problem as in [1]. We show that when $X=(X_1,X_2)$, where $X_2$ is a deterministic function of $X_1$, the upper bounds on ${\mathbb{L}}^b(P_{XY},M,0)$ can be improved by using a shorter shared key size, i.e., $M<|\mathcal{X}|$. In the next theorem, we provide upper bounds on ${\mathbb{L}}^b(P_{XY},M,0)$.

Theorem 13.

Let $X=(X_1,X_2)$, where $X_2=f(X_1)$, and the shared key size be $|{\mathcal{X}}_1|$. We have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_1|,0)\le \sum _{x_1\in {\mathcal{X}}_1}H(Y|X_1=x_1)+1+\lceil log(|{\mathcal{X}}_1|)\rceil ,\hfill \end{array}$$

(91)

if $|\mathcal{Y}|$ is finite, then

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_1|,0)\le \lceil log\left(|\mathcal{X}|(|\mathcal{Y}|-1)+1\right)\rceil +\lceil log(|{\mathcal{X}}_1|)\rceil +1,\hfill \end{array}$$

(92)

and if $X=(X_1,X_2)$ is deterministic function of Y, we obtain

$$\begin{array}{c}\hfill {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_1|,0)\le \lceil log\left(|\mathcal{Y}|-|\mathcal{X}|+1\right)\rceil +\lceil log(|{\mathcal{X}}_1|)\rceil +1.\end{array}$$

(93)

Proof. 

The proof is provided in Appendix B.  □

Remark 19.

Clearly, when $X=(X_1,X_2)$ with $X_2=f(X_1)$ the upper bounds (91), (92) and (93) improve the bounds in ([1], Theorem 8).

• Special Case: $X=(X_1,X_2)$ and $X_2=f(X_1)$

In this part, we use similar approaches as used in Theorems 12 and 13 to find upper bounds. We encode $X_1$ using one-time-pad coding and the same U as in Theorem 13. As shown in Theorem 13, $X_1$ is sufficient to decode Y, since $X_2=f(X_1)$; however, in this scheme, we do not have the possibility that we are allowed to leak about X. Similarly to Theorem 13, we obtain

$$\begin{array}{c}\hfill {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}_1|,ϵ)\le \sum _{x\in \mathcal{X}}H(Y|X=x)+1+\lceil log(|{\mathcal{X}}_1|)\rceil \\ \hfill =\sum _{x_1\in {\mathcal{X}}_1}H(Y|X_1=x_1)+1+\lceil log(|{\mathcal{X}}_1|)\rceil .\end{array}$$

Next, we use the separation technique as used in Theorem 12. For any $ϵ\ge 0$, if a separation exist such that $ϵ\ge H(X_1^{\prime })$, where $X_1=(X_1^{\prime },X_1^{″})$, we obtain

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},|{\mathcal{X}}^{″}|,ϵ)\le \sum _{x_1\in {\mathcal{X}}_1}H(Y|X_1=x_1)+H(X_1^{\prime })+2+\lceil log(|{\mathcal{X}}_1^{″}|)\rceil .\hfill \end{array}$$

Furthermore, we can take the minimum over all possible separations to improve the upper bound. Let ${\mathcal{S}}_{X_1}^{ϵ}$ be all possible separations, where $ϵ\ge H(X_1^{\prime })$. We have

$$\begin{array}{cc}\hfill & {\mathbb{L}}^b(P_{XY},\alpha ,ϵ)\le \sum _{x_1\in {\mathcal{X}}_1}H(Y|X_1=x_1)+2+\underset{(X_1^{\prime },X_1^{″})\in {\mathcal{S}}_{X_1}^{ϵ}}{min}\left\{H(X_1^{\prime })+\lceil log(|{\mathcal{X}}_1^{″}|)\rceil \right\},\hfill \end{array}$$

where $\alpha =|{arg\; min}_{X_1^{″}:(X_1^{\prime },X_1^{″})\in {\mathcal{S}}_{X_1}^{ϵ}}H(X_1^{\prime })+\lceil log(|{\mathcal{X}}_1^{″}|)\rceil |<|{\mathcal{X}}_1|$.

We can see that the upper bound on ${\mathbb{L}}^b(P_{XY},|{\mathcal{X}}^{″}|,ϵ)$ can be less than the bound in (91). For instance, let $H(X_1^{\prime })+2\le log(|{\mathcal{X}}_1^{\prime }|)$. Using the same arguments as in Remark 15, we have $H(X_1^{\prime })+1+\lceil log(|{\mathcal{X}}_1^{″}|)\rceil \le \lceil log(|{\mathcal{X}}_1|)\rceil$. Hence, if the leakage is more than a certain threshold, this can help us to improve the upper bound and send shorter codewords compared to the perfect privacy case. Moreover, it helps us to use a shorter shared secret key size.

5. Applications: Cache-Aided Networks

In this part, we present an application where the results of this paper can be used. The complete study of the application can be found in [49]. To do so, let us consider the scenario illustrated in Figure 7. A server has access to a database consisting of N files $Y_1,\dots ,Y_N$, where each file, of size F bits, is sampled from the joint distribution $P_{X{Y}_1·Y_N}$. The random variable X denotes the private latent variable. We assume that the server knows the realization of the private variable X as well. The server is connected to K users over a shared link, where user i has access to a local cache memory of size $MF$ bits. Furthermore, we assume that the server and the users have access to a shared secret key denoted by W, of size T. The system works in two phases: the placement and delivery phases, respectively [50]. In the placement phase, the server fills the local caches using the database. Let $Z_k$ denote the content of the local cache memory of user k, $k\in \left[K\right]\triangleq \{1,\dots ,K\}$ after the placement phase. In the delivery phase, first the users send their demands to the server, where $d_k\in \left[N\right]$ denotes the demand of user k. The server sends a response, denoted by $\mathcal{C}$, over the shared link to satisfy all the demands, simultaneously. We assume that an adversary has access to the shared link as well, and uses $\mathcal{C}$ to extract information about X. However, the adversary does not have access to the local cache contents or the secret key. Since the files in the database are all correlated with the private latent variable X, the coded caching and delivery techniques introduced in [50] do not satisfy the privacy requirement. The goal of the cache-aided private delivery problem is to find a response $\mathcal{C}$ with minimum possible average length that satisfies a certain privacy constraint and the zero-error decodability constraint of the users. Here, we consider the worst-case demand combinations $d=(d_1,\dots ,d_K)$ to construct $\mathcal{C}$. This expectation is taken for the randomness in the database. In this study, we first consider a perfect privacy constraint, i.e., we require $\mathcal{C}$ to be independent of X. Let ${\widehat{Y}}_{d_k}$ denote the decoded message of user k using W, $\mathcal{C}$, and $Z_k$. User k should be able to recover $Y_{d_k}$ reliably, i.e., $\mathbb{P}\{{\widehat{Y}}_{d_k}\ne Y_{d_k}\}=0$, $\forall k\in \left[K\right]$. We remark that we have a cache-aided variable-length compression problem with a privacy constraint. Hence, to solve this problem and design the code $\mathcal{C}$, we utilized techniques used in privacy mechanisms, data compression, and cache design and coded delivery problems, and combined them to build such a code. In particular, we used the data compression techniques employed in this paper and caching design techniques in [50]. Finally, we extended the results for correlated X and $\mathcal{C}$, i.e., when non-zero leakage is allowed. To do so, we used the results of this paper for correlated X and $\mathcal{C}$, i.e., the non-perfect privacy part. For more details, see [49].

6. Experiment

In this section, we provide an experiment to evaluate the bounds obtained in Theorem 4. To do so, we used the MNIST dataset, which contains 60,000 images illustrating handwritten digits from 0 to 9. Let the RV S (information source) denote the images in the dataset, i.e., $|\mathcal{S}|=$ 60,000. Let Y represent the useful data that is a feature extracted from the dataset. In this example, the useful data are defined as a “quantized histogram”. To determine the quantized histogram of the dataset, we first converted the images into black and white by quantizing them. The histogram of any image in the dataset is then computed as the ratio of the number of white pixels to the total number of pixels. Consequently, the histogram of any image can be represented by a value within the interval $[0,1]$. For quantizing the histogram of any image, we used the following intervals: Interval 1 $=[0,0.1)$, Interval 2 $=[0.1,0.15)$, Interval 3 $=[0.15,0.2)$, Interval 4 $=[0.2,0.25)$, Interval 5 $=[0.25,0.3)$, Interval 6 $=[0.3,0.35)$ and Interval 7 $=[0.35,1]$. Each image in the dataset was therefore labeled with a number between 1 and 7, indicating the interval to which its histogram belongs. Let Y denote the interval sample S belongs to. Clearly, the labels of the intervals are deterministic functions of the information source S. For instance, in Figure 8, the number of white pixels is 130, hence the quantized histogram is equal to $0.1658$, which corresponds to the third interval.

Let the RV Z denote the label of each image that is a number from 0 to 9, indicating the digit which the image represents, i.e., $Z\in \{0,1,\dots ,9\}$. Clearly, Z is a deterministic function of S, i.e., $Z=f(S)$. The private attribute X is defined as the presence of, digit 0 which is a binary RV, i.e., $X\in \{0,1\}$ and $X=\left\{\begin{array}{c}1\mathrm{if}Z=0,\hfill \\ 0\mathrm{if}Z=1\hfill \end{array}\right.$. Here, we use an empirical distribution for Z and it can be seen that X is a deterministic function of Z, which yields the Markov chain $X-Z-Y$. Using this Markov chain, the kernel $P_{X|Y}$ can be obtained as $P_{X|Z}{P}_{Z|Y}$, where

$$\begin{array}{c}\hfill P_{X|Z}=\left[\begin{array}{ccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right],\end{array}$$

and $P_{Z|Y}$ can be found from the dataset. We used an empirical distribution to find the kernel $P_{Y|Z}$, e.g., $P_{Y=1|Z=1}$ is the number of images illustrating digit 1, which corresponds to label 1 (their quantized histograms belong to the first interval) divided by the total number of images with digit 1. By using $P_{Y|Z}$ derived in (94) and multiplying it by $P_{Z|X}$, we obtain $P_{X|Y}$ as in (95).

$$\begin{array}{c}\hfill P_{Z|Y}=\left[\begin{array}{ccccccc}0.0064& 0.0441& 0.1445& 0.3070& 0.4678& 0.5968& 0.7500\\ 0.4922& 0.0497& 0.0037& 0.0004& 0& 0& 0\\ 0.0262& 0.0854& 0.1440& 0.1599& 0.1044& 0.1129& 0\\ 0.0416& 0.1017& 0.1339& 0.1265& 0.0922& 0.0323& 0\\ 0.0876& 0.1330& 0.0796& 0.0332& 0.0111& 0& 0\\ 0.0712& 0.1058& 0.0907& 0.0676& 0.0478& 0.0161& 0\\ 0.0479& 0.1086& 0.1181& 0.0973& 0.0711& 0.0645& 0\\ 0.1330& 0.1447& 0.0635& 0.0201& 0.0078& 0& 0\\ 0.0162& 0.0872& 0.1409& 0.1523& 0.1700& 0.1774& 0.2500\\ 0.0778& 0.1396& 0.0812& 0.0357& 0.0278& 0& 0\end{array}\right],\end{array}$$

(94)

$$\begin{array}{c}\hfill P_{X|Y}=\left[\begin{array}{ccccccc}0.0064& 0.0441& 0.1445& 0.3070& 0.4678& 0.5968& 0.7500\\ 0.9936& 0.9559& 0.8555& 0.6930& 0.5322& 0.4032& 0.2500\end{array}\right].\end{array}$$

(95)

Moreover, the distribution of the task Y is given as in

Table 1. Marginal distribution of the useful data Y.

	$y=1$	$y=2$	$y=3$	$y=4$	$y=5$
$\mathrm{Pr}(Y=y)$	$0.1851$	$0.4069$	$0.2981$	$0.0936$	$0.0151$
	$y=6$	$y=7$
$\mathrm{Pr}(Y=y)$	$0.0010$	$0.0002$

.

The goal was to compress Y and send it to a user, and we considered a perfect privacy case where the privacy leakage was zero. Since X is a deterministic function of Y, we have $h_0(P_{XY})=g_0(P_{XY})$ and $P_{XY}\in {\widehat{\mathcal{P}}}_{XY}$. Hence, using the linear program in [15], we found U that achieved $g_0(P_{XY}$, and $\mathcal{K}(P_{XY})$ was obtained. Using Theorem 4, the average length of $\mathcal{C}$ was 2.88 bits; however, using the method in [1], 4.16 bits were required to send the message $\mathcal{C}$ over the channel.

7. Conclusions

We have studied a compression problem with a privacy constraint in two scenarios, where the information delivered over the channel is either independent of X or is correlated with X, satisfying a bounded leakage constraint. Considering the perfect privacy constraint, we proposed new upper bounds using a two-part construction coding that benefits from the solution of $g_0(P_{XY})=h_0(P_{XY})$ to encode the second part of the code. For the first part of the code, we hide the private data using one-time pad coding. Furthermore, in case of $|\mathcal{Y}|\ge |\mathcal{X}|$, we proposed a new achievable scheme. We have shown that the new upper bounds can improve the existing ones. Moreover, we strengthened the bounds using the greedy entropy-based algorithm. Considering the second scenario, we obtained upper and lower bounds and showed that the upper bounds can be asymptotically tight. To achieve the upper bounds, we used two-part construction coding. Furthermore, in the case of perfect privacy, we showed that, by using the separation technique, the previous upper bounds can be improved.