# Information Leakage in Index Coding

Yucheng Liu† This work was supported by the ARC Discovery Scheme DP190100770;
the US National Science Foundation Grant CNS-1815322; and the ARC Future
Fellowship FT190100429.  Lawrence Ong† Phee Lep Yeoh§ Parastoo Sadeghi‡ Joerg
Kliewer∗ and Sarah Johnson†
†The University of Newcastle  Australia (emails: {yucheng.liu  lawrence.ong
<EMAIL_ADDRESS>
§University of Sydney  Australia (email<EMAIL_ADDRESS>
‡University of New South Wales  Canberra  Australia (email:
<EMAIL_ADDRESS>
∗New Jersey Institute of Technology  USA (email<EMAIL_ADDRESS>

###### Abstract

We study the information leakage to a guessing adversary in index coding with
a general message distribution. Under both vanishing-error and zero-error
decoding assumptions, we develop lower and upper bounds on the optimal leakage
rate, which are based on the broadcast rate of the subproblem induced by the
set of messages the adversary tries to guess. When the messages are
independent and uniformly distributed, the lower and upper bounds match,
establishing an equivalence between the two rates.

##  I Introduction

Index coding [1, 2] studies the communication problem where a server
broadcasts messages via a noiseless channel to multiple receivers with side
information. Due to its simple yet fundamental model, index coding has been
recognized as a canonical problem in network information theory, and is
closely connected with many other problems such as network coding, distributed
storage, and coded caching. Despite substantial progress achieved so far (see
[3] and the references therein), the index coding problem remains open in
general.

In secure index coding [4, 5, 6, 7], the server must simultaneously satisfy
the legitimate receivers’ decoding requirements and protect the content of
some messages from being obtained by an eavesdropping adversary. A variant of
this setup puts security constraints on the receivers themselves against some
messages [4, 8, 9]. Instead of protecting the messages, another variant of
index coding has also been studied from a privacy-preserving perspective,
where the goal is to limit the information that a receiver can infer about the
_identities_ of the requests of other receivers [10]. The privacy-utility
tradeoff in a multi-terminal data publishing problem inspired by index coding
was investigated in [11].

In this work, we study the information leakage to a guessing adversary in
index coding, which, to the best of our knowledge, has not been considered in
the literature. The adversary eavesdrops the broadcast codeword and tries to
guess the message tuple via maximum likelihood estimation within a certain
number of trials. Our aim is to characterize the information leakage to the
adversary, which is defined as the ratio between the adversary’s probability
of successful guessing _after and before_ observing the codeword [12, 13, 14].
For a visualization of the problem setup, see Figure 1.

Figure 1: There are two correlated binary messages
$X_{\\{1,2\\}}=(X_{1},X_{2})$ with distribution: $P_{X_{\\{1,2\\}}}(0,0)=0.1$,
$P_{X_{\\{1,2\\}}}(0,1)=0.2$, $P_{X_{\\{1,2\\}}}(1,0)=0.3$, and
$P_{X_{\\{1,2\\}}}(1,1)=0.4$. A binary codeword $Y$ is generated by the server
as $Y=X_{1}\oplus X_{2}$ and broadcast to the receivers. Every receiver can
decode its wanted message based on the codeword and its side information. An
adversary eavesdrops the codeword $Y$ and makes a single guess on
$X_{\\{1,2\\}}$. If $Y=0$, the adversary’s guess will be $(1,1)$ as
$P_{X_{\\{1,2\\}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Y}(1,1\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}0)=0.8>P_{X_{\\{1,2\\}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Y}(0,0\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}0)=0.2>P_{X_{\\{1,2\\}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Y}(0,1\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}0)=P_{X_{\\{1,2\\}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Y}(1,0\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}0)=0$.
Similarly, if $Y=1$, the adversary’s guess will be $(1,0)$.

Recently we have studied [15] information leakage to a guessing adversary in
zero-error source coding defined by a family of confusion graphs [16]. While
the index coding problem can also be characterized by a confusion graph family
[17], the study of information leakage in index coding is intrinsically
different from that of source coding in the following aspects. The most
significant difference comes from the different internal structures within the
two confusion graph families. More specifically, for the source coding model
we considered [15], the relationship among the confusion graphs of different
sequence lengths is characterized by the disjunctive product [18]. On the
other hand, for the index coding problem, the relationship among the confusion
graphs cannot be characterized by any previously defined graph product.
Another difference is that while our previous work [15] requires zero-error
decoding at the legitimate receiver assuming _worst-case_ source distribution,
this paper considers both zero-error and vanishing-error scenarios and assume
a _general_ message distribution. Furthermore, in this work we take into
account the adversary’s side information which can include any message in the
system.

Our main contribution is developing lower and upper bounds (i.e., converse and
achievability results) on the optimal information leakage rate, for both
vanishing-error and zero-error scenarios. The converse bound is derived using
graph-theoretic techniques based on the notion of confusion graphs for index
coding [17]. The achievability result is established by constructing a
deterministic coding scheme as a composite of the coding schemes for two
subproblems, one induced by the messages the adversary knows as side
information and the other induced by the messages the adversary does not know
and thus tries to guess.

Moreover, we show that when the messages are uniformly distributed and
independent of each other (as in most existing works for index coding), the
lower and upper bounds developed match. This establishes an equivalence
between the optimal leakage rate of the problem and the optimal compression
rate of the subproblem induced by the messages the adversary tries to guess.

##  II System Model and Problem Formulation

Notation: For any $a\in{\mathbb{Z}}^{+}$, $[a]\doteq\\{1,2,\cdots,a\\}$. For
any discrete random variable $Z$ with probability distribution $P_{Z}$, we
denote its alphabet by $\mathcal{Z}$ with realizations $z\in\mathcal{Z}$.

There are $n$ discrete memoryless stationary messages (sources),
$X_{i},i\in[n]$, of some common finite alphabet $\mathcal{X}$. For any
$S\subseteq[n]$, set ${X}_{S}\doteq(X_{i},i\in S)$, ${x}_{S}\doteq(x_{i},i\in
S)$, and
$\mathcal{X}_{S}\doteq\mathcal{X}^{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}S\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}$.
Thus $X_{[n]}$ denotes the tuple of all $n$ messages, and
$x_{[n]}\in\mathcal{X}_{[n]}$ denotes a realization of the message $n$-tuple.
By convention,
$X_{\emptyset}=x_{\emptyset}=\mathcal{X}_{\emptyset}=\emptyset$. We consider
an arbitrary, but fixed distribution $P_{X_{[n]}}$ on $\mathcal{X}_{[n]}$,
assuming without loss of generality that it has full support111While a common
assumption in most index coding literatures is that the messages are
independent and uniformly distributed, here we consider the more general case
with arbitrary joint distribution for the messages..

There is a server containing all messages. It encodes the tuple of $n$ message
sequences $X^{t}_{[n]}=(X^{t}_{i},i\in[n])$ according to some (possibly
randomized) encoding function $f$ to some codeword $Y$ that takes values in
the code alphabet $\mathcal{Y}=\\{1,2,\ldots,M\\}$. Each message sequence
$X^{t}_{i}=(X_{i,1},X_{i,2},\ldots,X_{i,t})$ is of length $t$ symbols. The
server then transmits the codeword to $n$ receivers via a noiseless broadcast
channel of normalized unit capacity. Let $P_{Y,X^{t}_{[n]}}$ denote the joint
distribution of the message sequence tuple $X^{t}_{[n]}$ and the codeword $Y$.
For any $S\subseteq[n]$, we define the following notation for message sequence
tuples.

  * $\bullet$

$\mathcal{X}^{t}_{S}=\mathcal{X}^{t\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}S\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}$;

  * $\bullet$

$X^{t}_{S}=(X^{t}_{i},i\in S)=(X_{S,1},X_{S,2},\ldots,X_{S,t})$, where
$X_{S,j}=(X_{i,j},i\in S)$ for every $j\in[t]$. Note that $X_{i,j}$ denotes
the $j$-th symbol of message sequence $X^{t}_{i}$.

  * $\bullet$

Similarly, $x^{t}_{S}=(x^{t}_{i},i\in S)=(x_{S,j},j\in[t])$, where
$x_{S,j}=(x_{i,j},i\in S)$ for every $j\in[t]$.

Also, as the messages are memoryless, for any
$x^{t}_{[n]}=(x_{[n],1},x_{[n],2},\ldots,x_{[n],t})$,
$P_{X^{t}_{[n]}}(x^{t}_{[n]})=\prod_{j\in[t]}P_{X_{[n]}}(x_{[n],j})$.

On the receiver side, we assume that receiver $i\in[n]$ wishes to obtain
message $X^{t}_{i}$ and knows $X^{t}_{A_{i}}$ as side information for some
$A_{i}\subseteq[n]\setminus\\{i\\}$.

More formally, a $(t,M,f,{\bf g})$ index code can be defined by

  * $\bullet$

One stochastic encoder $f\mathchar
58\relax\mathcal{X}^{nt}\to\\{1,2,\ldots,M\\}$ at the server that maps each
message sequence tuple ${x}^{t}_{[n]}\in\mathcal{X}^{nt}$ to a codeword
$y\in\\{1,2,\ldots,M\\}$, and

  * $\bullet$

$n$ deterministic decoders ${\bf g}=(g_{i},i\in[n])$, one for each receiver
$i\in[n]$, such that $g_{i}\mathchar
58\relax\\{1,2,\ldots,M\\}\times\mathcal{X}^{t\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}A_{i}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}\to\mathcal{X}^{t}$
maps the codeword $y$ and the side information ${x}^{t}_{A_{i}}$ to some
estimated sequence $\hat{x}^{t}_{i}$.

For any $\epsilon>0$, we say a $(t,M,f,{\bf g})$ index code is _valid_ (with
respect to $\epsilon$) if and only if (iff) the average probability of error
satisfies ${\rm P}_{\rm e}\doteq{\rm
P}\\{({\hat{X}}_{[n]})\neq(X_{[n]})\\}\leq\epsilon$. We say a compression rate
$R$ is achievable iff for every $\epsilon>0$, there exists a valid
$(t,M,f,{\bf g})$ code such that $R\geq(\log M)/t$.

The _optimal_ compression rate $\mathcal{R}$, also referred to as the
_broadcast rate_ , can be defined as

$\displaystyle\mathcal{R}$ $\displaystyle=\lim_{\epsilon\to
0}\lim_{t\to\infty}\inf_{\begin{subarray}{c}\text{valid $(t,M,f,{\bf g})$
code}\end{subarray}}\frac{\log M}{t}.$ (1)

We say a $(t,M,f,{\bf g})$ code is valid with respect to zero-error decoding
iff the average probability of error is zero. The zero-error broadcast rate
$\rho$ can then be defined as

$\displaystyle\rho\doteq\lim_{t\to\infty}\inf_{\begin{subarray}{c}\text{valid
$(t,M,f,{\bf g})$ code w.r.t.}\\\ \text{zero-error
decoding}\end{subarray}}\frac{\log M}{t}.$ (2)

Clearly, by definition, we always have $\mathcal{R}\leq\rho$.

The side information availability at receivers for a specific index coding
instance can be represented by a sequence
$(i\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}j\in A_{i}),i\in[n]$.
Alternatively, it can be characterized by a family of _confusion graphs_ ,
$(\Gamma_{t},t\in{\mathbb{Z}}^{+})$ [17]. For a given sequence length $t$, the
confusion graph $\Gamma_{t}$ is an undirected graph defined on the message
sequence tuple alphabet $\mathcal{X}^{t}_{[n]}$. That is,
$V(\Gamma_{t})=\mathcal{X}^{t}_{[n]}$. Vertex $x^{t}_{[n]}$ in $\Gamma$
corresponds to the realization $x^{t}_{[n]}$. Any two different vertices
$x^{t}_{[n]},z^{t}_{[n]}$ are adjacent in $\Gamma_{t}$ iff $x^{t}_{i}\neq
z^{t}_{i}$ and $x^{t}_{A_{i}}=z^{t}_{A_{i}}$ for some receiver $i\in[n]$. We
call any pair of vertices satisfying this condition _confusable_. Hence,
$E(\Gamma_{t})=\\{\\{x^{t}_{[n]},z^{t}_{[n]}\\}\mathchar
58\relax\text{$x^{t}_{i}\neq z^{t}_{i}$ and $x^{t}_{A_{i}}=z^{t}_{A_{i}}$ for
some $i\in[n]$}\\}$.

For correct decoding at all receivers, any two realizations
$x^{t}_{[n]},z^{t}_{[n]}$ can be mapped to the same codeword $y$ with nonzero
probabilities iff they are not confusable [17]. See Figure 2 below for a toy
example of an index coding instance and its confusion graph. For the
definitions for basic graph-theoretic notions, see any textbook on graph
theory (e.g., Scheinerman and Ullman [18]).

Figure 2: The confusion graph $\Gamma_{1}$ with $t=1$ for the $3$-message
index coding instance
$(1\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}-),(2\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}3),(3\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}2)$.
Note that, for example, $x_{[n]}=(0,0,0)$ and $z_{[n]}=(0,0,1)$ are confusable
because $x_{3}=0\neq z_{3}=1$ and $x_{A_{3}}=x_{2}=0=z_{2}=z_{A_{3}}$. Suppose
$(0,0,0)$ and $(0,0,1)$ are mapped to the same codeword $y$ with certain
nonzero probabilities. Then upon receiving this $y$, receiver $3$ will not be
able to tell whether the value for $X_{3}$ is $0$ or $1$ based on its side
information of $X_{2}=0$. For this graph, it can be easily verified that the
independence number is $2$, and that the chromatic number equals to the
fractional chromatic number, both of which equal to $4$. We have drawn an
optimal coloring scheme with $4$ colors in the graph.

Consider any set $S\subseteq[n]$. The subproblem induced by $S$ is jointly
characterized by the distribution $P_{X_{S}}$ and the sequence
$(i\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}A_{i}\cap S),i\in S$.
Let $\Gamma_{t}(S)$ denote the confusion graph of sequence length $t$ of the
subproblem induced by $S$. Let $\mathcal{R}(S)$ and $\rho(S)$ denote the
broadcast rate and zero-error broadcast rate of the subproblem induced by $S$,
respectively.

Preliminaries on $\mathcal{R}$ and $\rho$: Consider any index coding problem
characterized by confusion graphs $(\Gamma_{t},t\in{\mathbb{Z}}^{+})$ and
distribution $P_{X_{[n]}}$. We start with the following lemma.

###### Lemma 1

To characterize the broadcast rate $\mathcal{R}$ and zero-error broadcast rate
$\rho$, it suffices to only consider index codes with deterministic encoding
function $f$.

The above lemma can be simply proved by showing that given any valid index
code with a stochastic encoding function, one can construct another valid code
with a deterministic encoding function and same or smaller compression rate.

Most existing results in the literature on the optimal compression rate
(vanishing or zero error) of index coding were established assuming
deterministic encoding functions. Lemma 1 indicates that those results can be
directly applied to characterizing $\mathcal{R}$ and $\rho$.

Since we are considering fixed-length codes (rather than variable-length
codes), the zero-error broadcast rate $\rho$ does not depend on $P_{X_{[n]}}$
and can be characterized solely by the confusion graphs
$(\Gamma_{t},t\in{\mathbb{Z}}^{+})$ [17] as

$\displaystyle\rho=\lim_{t\to\infty}\frac{1}{t}\log\chi(\Gamma_{t})\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(a)}$\hss}}}}{{=}}\lim_{t\to\infty}\frac{1}{t}\log\chi_{\rm
f}(\Gamma_{t}),$ (3)

where $\chi(\cdot)$ and $\chi_{\rm f}(\cdot)$ respectively denote the
chromatic number and fractional chromatic number of a graph, and the proof of
$(a)$ can be found in [3, Section 3.2].

It has been shown [19] that, with the messages $X_{[n]}$ being uniformly
distributed and independent of each other, the vanishing-error broadcast rate
$\mathcal{R}$ equals to the zero-error broadcast rate $\rho$. Such equivalence
does not hold for a general distribution $P_{X_{[n]}}$ as it has been shown in
[20] that the (vanishing-error) broadcast rate $\mathcal{R}$ can be strictly
smaller than its zero-error counterpart $\rho$.

Leakage to a guessing adversary:

We assume the adversary knows messages $X_{P}$ and tries to guess the
remaining messages $X_{Q}$, where $Q=[n]\setminus P$, via maximum likelihood
estimation within a number of trials. In other words, the adversary generates
a list of certain size of guesses, and is satisfied iff the true message
sequence is in the list. We characterize the number of guesses the adversary
can make by a function of sequence length, $c\mathchar
58\relax{\mathbb{Z}}^{+}\to{\mathbb{Z}}^{+}$, namely, the guessing capability
function. We assume $c(t)$ to be non-decreasing and upper-bounded222It can be
verified that if for some $t$ we have $c(t)>\alpha(\Gamma_{t}(Q))$, then the
probability of the adversary successfully guessing $x^{t}_{Q}$ after observing
$y$ is at least $1-{\rm P}_{\rm e}$, which tends to $1$ as $\epsilon$ tends to
$0$, making the problem trivial.  by $\alpha(\Gamma_{t}(Q))$, where
$\alpha(\cdot)$ denotes the independence number of a graph.

Consider any valid $(t,M,f,{\bf g})$ index code. Before eavesdropping the
codeword $y$, the expected probability of the adversary successfully guessing
$x^{t}_{Q}$ with $c(t)$ number of guesses is

$\displaystyle{\rm P_{\rm
s}}(X^{t}_{P})={\mathbb{E}}_{X^{t}_{P}}\left[\max_{K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)}\sum_{x^{t}_{Q}\in
K}P_{X^{t}_{Q}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}X^{t}_{P}}(x^{t}_{Q}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}X^{t}_{P})\right],$

and the expected successful guessing probability after observing $y$ is

$\displaystyle{\rm P_{\rm
s}}(X^{t}_{P},Y)={\mathbb{E}}_{Y,X^{t}_{P}}\left[\max_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum_{x^{t}_{Q}\in
K}P_{X^{t}_{Q}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Y,X^{t}_{P}}(x^{t}_{Q}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Y,X^{t}_{P})\right].$

The leakage to the adversary, denoted by $L$, is defined as the logarithm of
the ratio between the expected probabilities of the adversary successfully
guessing $x_{Q}$ _after and before_ observing the transmitted codeword $y$.
That is,

$\displaystyle L\doteq\log\frac{{\rm P_{\rm s}}(X^{t}_{P},Y)}{{\rm P_{\rm
s}}(X^{t}_{P})}.$ (4)

The (optimal) leakage rate can then be defined as

$\displaystyle\mathcal{L}$ $\displaystyle\doteq\lim_{\epsilon\to
0}\lim_{t\to\infty}t^{-1}\inf_{\text{valid $(t,M,f,{\bf g})$ code}}L.$ (5)

###### Remark 1

It can be readily verified that the leakage metric $L$ is always non-negative.
When $c(t)=1$ (i.e., the adversary only makes a single guess after each
observation), $L$ reduces to the min-entropy leakage [12]. When $c(t)=1$ and
the messages are uniformly distributed, $L$ is equal to the maximal leakage
[14] and the maximum min-entropy leakage [13].

If we require zero-error decoding at receivers, the zero-error (optimal)
leakage rate $\lambda$ can be similarly defined as

$\displaystyle\lambda$
$\displaystyle\doteq\lim_{t\to\infty}t^{-1}\inf_{\begin{subarray}{c}\text{valid
$(t,M,f,{\bf g})$ code w.r.t.}\\\ \text{zero-error decoding}\end{subarray}}L.$
(6)

By definition, we always have $\mathcal{L}\leq\lambda$.

##  III Information Leakage in Index Coding

###  III-A Leakage Under A General Message Distribution

Consider any index coding problem
$(i\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}j\in A_{i}),i\in[n]$
with confusion graphs $(\Gamma_{t},t\in{\mathbb{Z}}^{+})$ and distribution
$P_{X_{[n]}}$. Our main result is the following theorem.

###### Theorem 1

For the vanishing-error leakage rate $\mathcal{L}$, we have

$\displaystyle\rho(Q)-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}+\log\frac{1}{\sum\limits_{x_{P}}\max\limits_{x_{Q}}P_{X_{[n]}}(x_{[n]})}\leq\mathcal{L}\leq\mathcal{R}(Q).$
(7)

For the zero-error leakage rate $\lambda$, we have

$\displaystyle\rho(Q)-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}+\log\frac{1}{\sum\limits_{x_{P}}\max\limits_{x_{Q}}P_{X_{[n]}}(x_{[n]})}\leq\lambda\leq\rho(Q).$
(8)

In the following, we prove the lower and upper bounds in (7). As for (8), the
lower bound follows directly from the lower bound in (7) and the fact that
$\mathcal{L}\leq\lambda$, and the upper bound can be shown using similar
techniques to the proof of the upper bound in (7).

###### Proof:

Consider any $\epsilon>0$ and any valid $(t,M,f,{\bf g})$ index code for which
${\rm P}_{\rm e}\leq\epsilon$.

Consider any codeword $y\in\mathcal{Y}$ and any realization
$x^{t}_{P}\in\mathcal{X}^{t}_{P}$. Let $G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$
denote the collection of realizations $x^{t}_{Q}$ such that
$(y,x^{t}_{P},x^{t}_{Q})$ has nonzero probability, and for the event that
$x^{t}_{[n]}=(x^{t}_{P},x^{t}_{Q})$ is the true message sequence tuple
realization and $y$ is the codeword realization, every receiver can correctly
decode its requested message. That is,

$\displaystyle
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})=\\{x^{t}_{Q}\in\mathcal{X}^{t}_{Q}\mathchar
58\relax g_{i}(y,x^{t}_{A_{i}})=x^{t}_{i},\forall i\in[n]\\}$

Then, we have

$\displaystyle\sum_{y,x^{t}_{P}}\sum_{x^{t}_{Q}\in
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})}P_{Y,X^{t}_{[n]}}(y,x^{t}_{P},x^{t}_{Q})$
$\displaystyle=1-{\rm P}_{\rm e}\geq 1-\epsilon.$ (9)

We also have

$\displaystyle\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq\alpha(\Gamma_{t}(Q)),$
(10)

which can be shown by contradiction as follows. Assume there exists two
different $x^{t}_{[n]},z^{t}_{[n]}\in\mathcal{X}^{t}_{[n]}$, such that
$x^{t}_{P}=z^{t}_{P}$, $x^{t}_{Q}\in G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$,
$z^{t}_{Q}\in G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$, and $x^{t}_{Q}$ and
$z^{t}_{Q}$ are adjacent (i.e., confusable) in $\Gamma_{t}(Q)$. Hence, there
exists some receiver $i\in Q$ such that $x^{t}_{i}\neq z^{t}_{i}$ and
$x^{t}_{A_{i}\cap Q}=z^{t}_{A_{i}\cap Q}$. Then considering $x^{t}_{[n]}$ and
$z^{t}_{[n]}$, since they have the same realizations for messages in $P$, we
have $x^{t}_{A_{i}}=(x^{t}_{A_{i}\cap P},x^{t}_{A_{i}\cap
Q})=(z^{t}_{A_{i}\cap P},z^{t}_{A_{i}\cap Q})=z^{t}_{A_{i}}$. From the
perspective of receiver $i$, upon receiving codeword $y$ and observing side
information $x^{t}_{A_{i}}=z^{t}_{A_{i}}$, it cannot tell whether the true
sequence for message $i$ is $x^{t}_{i}$ or $z^{t}_{i}$. Therefore, with the
transmitted codeword being $y$, either $x^{t}_{[n]}$ or $z^{t}_{[n]}$ being
the true realization will lead to an erroneous decoding at receiver $i$, which
contradicts the assumption that both $x^{t}_{Q}$ and $z^{t}_{Q}$ belong to
$G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$. Therefore, any realizations
$x^{t}_{Q},z^{t}_{Q}\in G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$ must be not
confusable and thus not adjacent to each other in $\Gamma_{t}(Q)$. In other
words, the vertex subset $G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\subseteq
V(\Gamma_{t}(Q))$ must be an independent set in $\Gamma_{t}(Q)$ and thus its
cardinality is upper bounded by the independence number of $\Gamma_{t}(Q)$.

We lower bound ${\rm P_{\rm s}}(X^{t}_{P},Y)$, i.e., the adversary’s expected
successful guessing probability after observing $Y$, as

$\displaystyle\sum_{y,x^{t}_{P}}\max_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum_{x^{t}_{Q}\in K}P_{Y,X^{t}_{[n]}}(y,x^{t}_{[n]})$
$\displaystyle\geq\sum_{y,x^{t}_{P}}\max_{\begin{subarray}{c}K\subseteq
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchar
58\relax\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum_{x^{t}_{Q}\in K}P_{Y,X^{t}_{[n]}}(y,x^{t}_{[n]})$
$\displaystyle\geq\sum_{y,x^{t}_{P}}\frac{1}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\begin{subarray}{c}K\subseteq
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchar
58\relax\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}=c(t)^{-}\end{subarray}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}$
$\displaystyle\qquad\sum_{\begin{subarray}{c}K\subseteq
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchar
58\relax\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}=c(t)^{-}\end{subarray}}\sum_{x^{t}_{Q}\in
K}P_{Y,X^{t}_{[n]}}(y,x^{t}_{[n]})$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(a)}$\hss}}}}{{=}}\sum_{y,x^{t}_{P}}\frac{\binom{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})-1\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}{c(t)^{-}-1}\sum\limits_{x^{t}_{Q}\in
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})}P_{Y,X^{t}_{[n]}}(y,x^{t}_{[n]})}{\binom{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}{c(t)^{-}}}$
$\displaystyle=\sum_{y,x^{t}_{P}}\frac{c(t)^{-}}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\sum_{x^{t}_{Q}\in
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})}P_{Y,X^{t}_{[n]}}(y,x^{t}_{[n]})$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(b)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(b)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(b)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(b)}$\hss}}}}{{\geq}}\frac{c(t)(1-\epsilon)}{\alpha(\Gamma_{t}(Q))},$
(11)

where
$c(t)^{-}=\min\\{c(t),\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\\}$,
and

  * $\bullet$

(a) follows from the fact that each $x^{t}_{Q}\in
G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$ appears in exactly
$\binom{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})-1\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}{c(t)^{-}-1}$
subsets of $G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})$ of size $c(t)^{-}$,

  * $\bullet$

(b) follows from (9), (10), and that if
$c(t)\leq\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$,
then
$\frac{c(t)^{-}}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}=\frac{c(t)}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}\geq\frac{c(t)}{\alpha(\Gamma_{t}(Q))}$,
otherwise we have
$c(t)>\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$
and thus
$\frac{c(t)^{-}}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}G_{\mathcal{X}^{t}_{Q}}(y,x^{t}_{P})\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}=1\geq\frac{c(t)}{\alpha(\Gamma_{t}(Q))}$,
where the inequality is due to the assumption that
$c(t)\leq\alpha(\Gamma_{t}(Q))$.

For bounding ${\rm P_{\rm s}}(X^{t}_{P})$, consider any two disjoint subsets
$A,B\subseteq[n]$. Note that any realization $x^{t}_{A}$ can be explicitly
denoted as $(x_{A,1},x_{A,2},\ldots,x_{A,t})$. We have

$\displaystyle\sum_{x^{t}_{A}}\max_{x^{t}_{B}}P_{X^{t}_{A\cup
B}}(x^{t}_{A},x^{t}_{B})$
$\displaystyle=\sum_{x^{t}_{A}}\max_{x^{t}_{B}}\prod_{j\in[t]}P_{X_{A\cup
B}}(x_{A,j},x_{B,j})$
$\displaystyle=\big{(}\sum_{x_{A}}\max_{x_{B}}P_{X_{A\cup
B}}(x_{A},x_{B})\big{)}^{t},$ (12)

where the last equality can be shown via induction.

Based on (11) and (12), we have

$\displaystyle\mathcal{L}$ $\displaystyle\geq\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\frac{\frac{c(t)(1-\epsilon)}{\alpha(\Gamma_{t}(Q))}}{\sum_{x^{t}_{P}}\max\limits_{K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)}\sum\limits_{x^{t}_{Q}\in K}P_{X^{t}_{[n]}}(x^{t}_{[n]})}$
$\displaystyle\geq\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\frac{\frac{c(t)(1-\epsilon)}{\alpha(\Gamma_{t}(Q))}}{c(t)\cdot\sum_{x^{t}_{P}}\max_{x^{t}_{Q}}P_{X^{t}_{[n]}}(x^{t}_{[n]})}$
$\displaystyle=\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\frac{\frac{(1-\epsilon)\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}V(\Gamma_{t}(Q))\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}{\alpha(\Gamma_{t}(Q))}\cdot\frac{1}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}V(\Gamma_{t}(Q))\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}}{(\sum_{x_{P}}\max_{x_{Q}}P_{X_{[n]}}(x_{[n]}))^{t}}$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(c)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(c)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(c)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(c)}$\hss}}}}{{=}}\lim_{t\to\infty}\frac{1}{t}\log\chi_{\rm
f}(\Gamma_{t}(Q))+\log\frac{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{X}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}^{-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}}{\sum_{x_{P}}\max_{x_{Q}}P_{X_{[n]}}(x_{[n]})}$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(d)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(d)}$\hss}}}}{{=}}\rho(Q)-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}+\log\frac{1}{\sum_{x_{P}}\max_{x_{Q}}P_{X_{[n]}}(x_{[n]})},$

where (c) follows from the fact that for any vertex-transitive graph $G$,
$\chi_{\rm
f}(G)=\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}V(G)\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}/\alpha(G)$
[18, Proposition 3.1.1], and that any confusion graph for index coding is
vertex-transitive [3, Section 11.4], and (d) follows from (3). ∎

###### Proof:

Consider any decoding error $\epsilon>0$. Construct a deterministic encoding
function $f$ that maps messages $X^{t}_{[n]}$ to codeword $Y=(Y_{1},Y_{2})$
according to the following rules.

  1. 1.

Codeword $Y_{1}$ is generated from $X^{t}_{P}$ according to some deterministic
encoding function $f_{1}\mathchar
58\relax\mathcal{X}^{t\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}P\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}\to\\{1,2,\ldots,\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{Y}_{1}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\\}$
such that there exist some decoding functions $g_{i},i\in P$ allowing zero-
error decoding for all receivers $i\in P$ and that
$t^{-1}\log\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{Y}_{1}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}=\rho(P)$.

  2. 2.

Codeword $Y_{2}$ is generated from $X^{t}_{Q}$ according to some deterministic
encoding function $f_{2}\mathchar
58\relax\mathcal{X}^{t\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}\to\\{1,2,\ldots,\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{Y}_{2}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\\}$
such that there exist some decoding functions $g_{i},i\in Q$ allowing
$\epsilon$-error decoding for all receivers $i\in Q$ and that
$t^{-1}\log\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{Y}_{2}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}=\mathcal{R}(Q)$.

Such encoding functions $f_{1}$ and $f_{2}$ exist for sufficiently large $t$.
We further verify that the coding scheme described above leads to an average
probability of error ${\rm P}_{\rm e}$ no more than $\epsilon$ and thus is
valid. Note that $f_{1}$ and $f_{2}$ are all deterministic. Define
$B_{\mathcal{X}^{t}_{Q}}=\\{x^{t}_{Q}\mathchar 58\relax\text{there exists some
$i\in Q$ such that $g_{i}(f_{2}(x^{t}_{Q}))\neq x^{t}_{i}$}\\}.$ That is,
$B_{\mathcal{X}^{t}_{Q}}$ denotes the set of $x^{t}_{Q}$ for which there is at
least one receiver $i\in Q$ that decodes erroneously. We have

$\displaystyle\epsilon\geq\sum_{x^{t}_{Q}\in
B_{\mathcal{X}^{t}_{Q}}}P_{X^{t}_{Q}}(x^{t}_{Q}).$ (13)

Hence, we have

$\displaystyle{\rm P}_{\rm e}$
$\displaystyle=\sum_{x^{t}_{P}}\sum_{x^{t}_{Q}\in
B_{\mathcal{X}^{t}_{Q}}}P_{X^{t}_{[n]}}(x^{t}_{[n]})$
$\displaystyle=\sum_{x^{t}_{Q}\in
B_{\mathcal{X}^{t}_{Q}}}P_{X^{t}_{Q}}(x^{t}_{Q})\sum_{x^{t}_{P}}P_{X^{t}_{P}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}X^{t}_{Q}}(x^{t}_{P}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}x^{t}_{Q})$
$\displaystyle=\sum_{x^{t}_{Q}\in
B_{\mathcal{X}^{t}_{Q}}}P_{X^{t}_{Q}}(x^{t}_{Q})\cdot 1\leq\epsilon,$

where the last inequality follows from (13). Now we have shown that the
proposed coding scheme is valid.

The optimal leakage rate is upper bounded by the rate of the information
leakage of the proposed coding scheme as $\epsilon$ goes to $0$. Let
$P_{Y,X^{t}_{[n]}}$ denote the joint distribution of $Y=(Y_{1},Y_{2})$ and
$X^{t}_{[n]}$ according to the proposed coding scheme. For any
$x^{t}_{P}\in\mathcal{X}^{t}_{P}$ and $y_{2}\in\mathcal{Y}_{2}$, define

$\displaystyle\mathcal{X}^{t}_{Q}(x^{t}_{P},y_{2})$
$\displaystyle=\\{x^{t}_{Q}\in\mathcal{X}^{t}_{Q}\mathchar 58\relax
P_{Y_{2},X^{t}_{[n]}}(y_{2},x^{t}_{P},x^{t}_{Q})>0\\},$

Then we have

$\displaystyle\mathcal{L}$ $\displaystyle\leq\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\frac{\sum\limits_{\begin{subarray}{c}x^{t}_{P},\\\
y_{1},y_{2}\end{subarray}}\max\limits_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum\limits_{x^{t}_{Q}\in
K}P_{Y,X^{t}_{[n]}}(y_{1},y_{2},x^{t}_{[n]})}{\sum\limits_{x^{t}_{P}}\max\limits_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum_{x^{t}_{Q}\in K}P_{X^{t}_{[n]}}(x^{t}_{[n]})}$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(a)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(a)}$\hss}}}}{{=}}\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\frac{\sum\limits_{x^{t}_{P},y_{2}}\max\limits_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}(x^{t}_{P},y_{2})\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum\limits_{x^{t}_{Q}\in
K}P_{X^{t}_{[n]}}(x^{t}_{[n]})}{\sum\limits_{x^{t}_{P}}\max\limits_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum\limits_{x^{t}_{Q}\in K}P_{X^{t}_{[n]}}(x^{t}_{[n]})}$
$\displaystyle\stackrel{{\scriptstyle\mathchoice{\hbox
to0.0pt{\hss$\displaystyle{(b)}$\hss}}{\hbox
to0.0pt{\hss$\textstyle{(b)}$\hss}}{\hbox
to0.0pt{\hss$\scriptstyle{(b)}$\hss}}{\hbox
to0.0pt{\hss$\scriptscriptstyle{(b)}$\hss}}}}{{\leq}}\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\frac{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{Y}_{2}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\cdot(\sum\limits_{x^{t}_{P}}\max\limits_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum\limits_{x^{t}_{Q}\in
K}P_{X^{t}_{[n]}}(x^{t}_{[n]}))}{\sum\limits_{x^{t}_{P}}\max\limits_{\begin{subarray}{c}K\subseteq\mathcal{X}^{t}_{Q}\mathchar
58\relax\\\
\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}K\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq
c(t)\end{subarray}}\sum\limits_{x^{t}_{Q}\in K}P_{X^{t}_{[n]}}(x^{t}_{[n]})}$
$\displaystyle=\lim_{\epsilon\to
0}\lim_{t\to\infty}\frac{1}{t}\log\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{Y}_{2}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}=\mathcal{R}(Q),$

where (a) follows from the definition of
$\mathcal{X}^{t}_{Q}(x^{t}_{P},y_{2})$ and the fact that $Y_{1}$ is a
deterministic function of $X^{t}_{P}$ and $Y_{2}$ is a deterministic function
of $X^{t}_{Q}$, and (b) follows from
$\mathcal{X}^{t}_{Q}(x^{t}_{P},y_{2})\subseteq\mathcal{X}^{t}_{Q}$. ∎

###### Remark 2

An interesting observation is that the bounds in Theorem 1 is independent of
the guessing capability function $c(t)$. Whether $\mathcal{L}$ and $\lambda$
depend on $c(t)$ remains unclear.

The upper and lower bounds in Theorem 1 do not match in general, as shown in
the following example.

Consider the $4$-message index coding problem
$(1\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}4),(2\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}3),(3\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}2),(4\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}1)$,
where the messages are binary and independent of each other with
$P_{X_{1}}(0)=1/4$ and $P_{X_{1}}(1)=3/4$, and $X_{2}$, $X_{3}$, and $X_{4}$
all follow a uniform distribution. Consider an adversary knowing $X_{P}=X_{4}$
as side information, and thus $Q=\\{1,2,3\\}$. The broadcast rate for the
subproblem induced by $Q$ has been previously found [20] to be
$\mathcal{R}(Q)=3-\frac{3}{4}\log 3$. By Theorem 1, the leakage rate
$\mathcal{L}$ is upper bounded by $\mathcal{R}(Q)$, and lower bounded as

$\displaystyle\mathcal{L}\geq$
$\displaystyle\rho(Q)-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}+\log\frac{1}{\sum_{x_{P}}\max_{x_{Q}}P_{X_{[n]}}(x_{[n]})}$
$\displaystyle=2-3+\log\frac{1}{3/32+3/32}=3-\log 3.$

Note that $\rho(Q)=2$ can be easily verified (for example, see [3, Section
8.6]). For the zero-error leakage rate $\lambda$, by (8) in Theorem 1, we have

$\displaystyle 3-\log 3\leq\lambda\leq 2.$

###  III-B Leakage Under A Uniform Message Distribution

In most existing works for index coding, the messages $X_{[n]}$ are assumed to
be uniformly distributed and thus independent of each other. In such cases,
Theorem 1 simplifies to the following corollary.

###### Corollary 1

If $P_{X_{[n]}}$ follows a uniform distribution, then

$\displaystyle\mathcal{L}=\lambda=\mathcal{R}(Q)=\rho(Q).$ (14)

###### Proof:

We have

$\displaystyle\rho(Q)-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}+\log\frac{1}{\sum_{x_{P}}\max_{x_{Q}}P_{X_{[n]}}(x_{[n]})}$
$\displaystyle=\rho(Q)-\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}Q\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}+\log\frac{1}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{X}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}^{t\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}P\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}}\cdot(1/\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{X}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}^{tn})}$
$\displaystyle=\rho(Q)=\mathcal{R}(Q),$

where the last equality follows from the fact that the vanishing-error and
zero-error broadcast rates are equal when messages are uniformly distributed
[19]. Combining Theorem 1 and the above result yields (14). ∎

###### Remark 3

Even though we have established the equivalence between the leakage and
broadcast rates under uniform message distribution, a computable single-letter
characterization of the value in (14) is unknown. Nevertheless, the
equivalence between the leakage and broadcast rates means that the extensive
results on the broadcast rate of index coding established in the literature
(such as single-letter lower and upper bounds, explicit characterization for
special cases, and structural properties) can be directly used to determine or
bound the leakage rate.

###### Remark 4

As the leakage rate in (14) can be achieved by the proposed coding scheme in
the achievability proof of Theorem 1, for any index coding instance with
uniform message distribution satisfying
$\mathcal{R}=\mathcal{R}(P)+\mathcal{R}(Q)$ (or equivalently,
$\rho=\rho(P)+\rho(Q)$), we know that the broadcast rate and leakage rate can
be simultaneously achieved by some deterministic index code.

## References

  * [1] Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over broadcast channels,” in _IEEE INFOCOM_ , Mar. 1998, pp. 1257–1264.
  * [2] Z. Bar-Yossef, Y. Birk, T. Jayram, and T. Kol, “Index coding with side information,” _IEEE Trans. Inf. Theory_ , vol. 57, pp. 1479–1494, 2011\.
  * [3] F. Arbabjolfaei and Y.-H. Kim, “Fundamentals of index coding,” _Foundations and Trends® in Communications and Information Theory_ , vol. 14, no. 3-4, pp. 163–346, 2018.
  * [4] S. H. Dau, V. Skachek, and Y. M. Chee, “On the security of index coding with side information,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 6, pp. 3975–3988, 2012.
  * [5] L. Ong, B. N. Vellambi, P. L. Yeoh, J. Kliewer, and J. Yuan, “Secure index coding: Existence and construction,” in _Proc. IEEE Int. Symp. on Information Theory (ISIT)_ , Barcelona, Spain, 2016, pp. 2834–2838.
  * [6] Y. Liu, Y.-H. Kim, B. Vellambi, and P. Sadeghi, “On the capacity region for secure index coding,” in _Proc. IEEE Information Theory Workshop (ITW)_ , Guanzhou, China, Nov. 2018.
  * [7] L. Ong, B. N. Vellambi, J. Kliewer, and P. L. Yeoh, “A code and rate equivalence between secure network and index coding,” _IEEE J. Sel. Areas Inf. Theory_ , vol. 2, no. 1, pp. 106–120, 2021.
  * [8] Y. Liu, P. Sadeghi, N. Aboutorab, and A. Sharififar, “Secure index coding with security constraints on receivers,” in _Proc. IEEE Int. Symp. on Information Theory and its Applications (ISITA)_ , Oct. 2020.
  * [9] V. Narayanan, J. Ravi, V. K. Mishra, B. K. Dey, N. Karamchandani, and V. M. Prabhakaran, “Private index coding,” _arXiv preprint arXiv:2006.00257_ , 2020.
  * [10] M. Karmoose, L. Song, M. Cardone, and C. Fragouli, “Privacy in index coding: $k$-limited-access schemes,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 5, pp. 2625–2641, 2019.
  * [11] Y. Liu, N. Ding, P. Sadeghi, and T. Rakotoarivelo, “Privacy-utility tradeoff in a guessing framework inspired by index coding,” in _Proc. IEEE Int. Symp. on Information Theory (ISIT)_ , Jun. 2020, pp. 926–931.
  * [12] G. Smith, “On the foundations of quantitative information flow,” in _International Conference on Foundations of Software Science and Computational Structures_. Springer, 2009, pp. 288–302.
  * [13] C. Braun, K. Chatzikokolakis, and C. Palamidessi, “Quantitative notions of leakage for one-try attacks,” _Electronic Notes in Theoretical Computer Science_ , vol. 249, pp. 75–91, 2009.
  * [14] I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 3, pp. 1625–1657, 2019\.
  * [15] Y. Liu, L. Ong, S. Johnson, J. Kliewer, P. Sadeghi, and P. L. Yeoh, “Information leakage in zero-error source coding: A graph-theoretic perspective,” in _Proc. IEEE Int. Symp. on Information Theory (ISIT)_ , Melbourne, Australia, 2021.
  * [16] J. Körner, “Coding of an information source having ambiguous alphabet and the entropy of graphs,” in _6th Prague Conference on Information Theory_ , 1973, pp. 411–425.
  * [17] N. Alon, E. Lubetzky, U. Stav, A. Weinstein, and A. Hassidim, “Broadcasting with side information,” in _49th Annu. IEEE Symp. on Foundations of Computer Science (FOCS)_ , Oct. 2008, pp. 823–832.
  * [18] E. R. Scheinerman and D. H. Ullman, _Fractional Graph Theory: A Rational Approach to the Theory of Graphs_. Courier Corporation, 2011.
  * [19] M. Langberg and M. Effros, “Network coding: Is zero error always possible?” in _Proc. 49th Ann. Allerton Conf. Comm. Control Comput._ , 2011, pp. 1478–1485.
  * [20] S. Miyake and J. Muramatsu, “Index coding over correlated sources,” in _Proc. IEEE Int. Symp. on Network Coding (NetCod)_ , Sydney, Australia, 2015, pp. 36–40.