Preserving Privacy while Broadcasting:
k -Limited-Access Schemes

arXiv:1705.08437v1 [cs.IT] 23 May 2017

Mohammed Karmoose, Linqi Song, Martina Cardone, Christina Fragouli
University of California Los Angeles, Los Angeles, CA 90095 USA
Email: {mkarmoose, songlinqi, martina.cardone, christina.fragouli}@ucla.edu
Abstract—Index coding employs coding across clients within
the same broadcast domain. This typically assumes that all clients
learn the coding matrix so that they can decode and retrieve
their requested data. However, learning the coding matrix can
pose privacy concerns: it may enable clients to infer information
about the requests and side information of other clients [1]. In
this paper, we formalize the intuition that the achieved privacy
can increase by decreasing the number of rows of the coding
matrix that a client learns. Based on this, we propose the use
of k-limited-access schemes: given an index coding scheme that
employs T transmissions, we create a k-limited-access scheme
with Tk ≥ T transmissions, and with the property that each
client learns at most k rows of the coding matrix to decode its
message. We derive upper and lower bounds on Tk for all values
of k, and develop deterministic designs for these schemes for
which Tk has an order-optimal exponent for some regimes.

I. I NTRODUCTION
Consider a server broadcasting publicly available messages
to clients, for instance YouTube videos. It is well recognized
that the use of coding and side information can offer significant
bandwidth savings when broadcasting [2]. However, it can
also pose privacy concerns [1]: although messages are publicly
available, clients may wish to preserve the anonymity of their
requests from other clients. A curious client, by leveraging the
broadcast information, may be able to infer what the requests
and side information of other clients are. In this paper, we
propose new schemes that seek to balance the bandwidth
benefits that coding offers with privacy considerations.
We pose this problem within the index coding framework [2]. In index coding, a server has m messages and can
losslessly broadcast to n clients. Each client requests a specific
message and may have a subset of the messages as side
information. To satisfy all clients with the minimum number
of transmissions T , the server can send coded broadcast
transmissions; the clients then use the coding matrix1 to
decode their messages. In [1], we showed that, by knowing
the coding matrix, a curious client can infer information about
the side information and requests of other clients.
This paper builds on a new observation: it may not be
necessary to provide clients with the entire coding matrix, but
with only the rows required for them to decode their own
message. For example, assume we have m = 4 messages and
n = 4 clients, where client i ∈ {1, 3} has message bi and
would like to receive message bi+1 , and client i ∈ {2, 4} has
1 The

coding matrix has size T × m and collects in each row the coding
coefficients used for the corresponding broadcast transmission.

message bi and would like to receive message bi−1 . The server
can satisfy all clients with two broadcast coded transmissions,
namely b1 + b2 and b3 + b4 , i.e., it uses a 2 × 4 coding matrix.
To decode their message, clients 1 and 2 only need to know
the first row of this matrix (the fact that the first combination
is b1 + b2 ), and similarly clients 3 and 4 only need to know
the second row of the matrix. By restricting the access to the
coding matrix, we limit the privacy leakage: the less rows a
client learns, the less it can infer about other clients.
We turn around this observation and ask: what if we restrict
each user to access at most k rows of the coding matrix? In
particular, assume we are given a coding matrix that uses T
transmissions to satisfy all clients. Can we “transform” it into
an “equivalent” coding matrix that potentially uses Tk ≥ T
transmissions to satisfy all clients, but where now each client
needs to learn at most k rows of it to decode its message?
We refer to the coding schemes that satisfy this condition as
k-limited-access schemes and we evaluate their benefits, cost
and feasibility. Our main contributions are:
1) Benefits: we formalize the intuition that the achieved level
of privacy can increase by decreasing the number of rows
of the coding matrix that a client learns.
2) Cost: we derive upper and lower bounds on Tk that
highlight the maximum and minimum cost to pay in terms
of additional broadcast transmissions as a function of k.
3) Feasibility: we propose deterministic designs for klimited-access schemes, for all values of k. For some
regimes, our designs provide values of Tk whose exponents are order-optimal.
The paper is organized as follows. Section II defines the
problem setup. Section III presents our main results, i.e., it
formalizes the intuition that privacy benefits can be achieved
by limiting clients’ access to the coding matrix, and it provides
upper and lower bounds on the number of transmissions
needed to satisfy clients when they know only part of the
matrix. Section IV proves the upper bounds presented in Section III by designing k-limited-access schemes and assessing
their performance. Section V positions our work with respect
to related literature and Section VI concludes the paper.
II. S ETUP AND P ROBLEM F ORMULATION
Notation. Calligraphic letters indicate sets; boldface lower
case letters denote vectors and boldface upper case letters
indicate matrices; |X | is the cardinality of X ; [n] is the set

of integers {1, · · · , n}; for all x ∈ R, the floor and ceiling
functions are denoted with bxc and dxe, respectively; 0j is the
all-zero row vector of dimension j; 1j denotes a row vector
of dimension j of all ones and Ij is the identity matrix of
dimension j; eji is the all-zero row vector of length j with a
1 in position i; logarithms are in base 2.
Index Coding. We consider an index coding instance, where
a server has a database B of m messages B = {bM }, where
M = [m] is the set of message indices, and bj ∈ FF
2 ,j ∈
M, with F being the message size. The server is connected
through a broadcast channel to a set of clients C = {cN },
where N = [n] is the set of client indices. We assume that
m ≥ n. Each client ci , i ∈ N , has a subset of the messages
{bSi }, with Si ⊂ M, as side information and requests a new
message bqi with qi ∈ M \ Si that it does not have. We
assume that the server employs a linear code, i.e., it designs a
set of broadcast transmissions that are linear combinations of
the messages in B. The linear index code can be represented
as AB = Y, where A ∈ FT2 ×m is the coding matrix, B ∈
Fm×F
is the matrix of all the messages and Y ∈ FT2 ×F is
2
the resulting matrix of linear combinations. Upon receiving
Y, client ci , i ∈ N , employs linear decoding to retrieve bqi .
Problem Formulation. In [2], it was shown that the index
coding problem is equivalent to the rank minimization of an
n × m matrix G ∈ Fn×m
whose i-th row gi , i ∈ [n], has the
2
following properties: (i) has a 1 in the position qi , (ii) has a 0
in the j-th position for all j ∈ M \ Si , (iii) can have either 0
or 1 in all the remaining positions. With this representation, ci
can successfully decode bqi using a linear combination of the
messages corresponding to the non-zero entries of gi . Finding
an optimal linear coding scheme (i.e., with minimum number
of transmissions) is equivalent to completing G so that it has
the minimum possible rank. Once we have one such G, we
can use a basis of the row space of G (of size T = rank (G))
as coding matrix A. In this case, in fact, client ci can construct
gi as a linear combination of the rows of A, i.e., ci performs
the decoding operation di AB = di Y, where di ∈ FT2 is the
decoding row vector of ci chosen such that di A = gi . We
remark that any index coding scheme that satisfies all clients
with T transmissions (where T is not necessarily optimal) –
and can be obtained by any index code design algorithm [3]–
[5] – corresponds to a completion of G (i.e., given A ∈ FT2 ×m ,
we can create a corresponding G in polynomial time).
In our problem formulation we assume we start with a given
matrix G of rank T , i.e., we are given n distinct vectors that
belong to a T -dimensional subspace. Using a basis of the row
space of the given G, we construct A ∈ FT2 ×m . Then, we ask:
Given n distinct vectors gi , i = [n], in a T -dimensional space,
can we find a minimum-size set Ak with Tk ≥ T vectors, such
that each gi can be expressed as a linear combination of at
most k vectors in Ak (with 1 ≤ k ≤ T )?
The vectors in Ak form the rows of the coding matrix Ak we
will employ. We can equivalently restate this as follows.
Given a coding matrix A, can we find P ∈ FT2 k ×T , with Tk
as small as possible, such that Ak = PA and each row in G

can be reconstructed by combining at most k rows of Ak ?
Note that k = T corresponds to the conventional transmission
scheme of an index coding problem for which P = IT .
Transmission Overhead. We note that the server can privately
share the (at most) k coding vectors that each ci needs
by using a private secret key or a dedicated channel (e.g.,
the same channel used by ci to convey the request qi to
the server). Thus, using a k-limited-access scheme incurs an
extra transmission overhead to privately convey the coding
vectors. In particular, the total number of transmitted bits
Ck is upper bounded by Ck ≤ nkm + Tk F, while the total
number of transmitted bits C using a conventional scheme is
C = T (F + m). We observe that the extra overhead incurred
is negligible in comparison to the broadcast transmissions
that convey the encoded messages when n and m are both
o(F ), which is a reasonable assumption for large file sizes
(for instance, when sharing YouTube videos).
III. M AIN R ESULTS
Consider the setup in the previous section and suppose
that client c1 is curious, i.e., by leveraging the k (linearly
independent) rows of Ak that it receives, it seeks to infer
information about ci , i ∈ [n], i 6= 1. We are interested in
quantifying the amount of information that c1 can obtain about
qi (i.e., the identity of the request of ci ) as a function of k.
As a first step towards this end, we define our privacy
metric as follows. We assume that the index coding instance is
random and we let L (respectively, L1 ) be the random variable
associated with the subspace spanned by the T rows of the
coding matrix A ∈ FT2 ×m (respectively, spanned by the k
vectors given to c1 ). Assume that c1 knows T . Then,
Definition III.1. The privacy metric is defined as
H (L|L1 , T ), i.e., it quantifies the amount of uncertainty
(entropy) that c1 has about the subspace spanned by the T
rows of the index coding matrix A.
The main motivation behind our choice of the privacy metric
is that it offers a yardstick for evaluating the amount of information that c1 can obtain about qi . This is because gi ∈ Fm
2
(that ci needs to recover bqi ) lies in the subspace spanned by
the T rows of A. Then, given the specific realizations T = t
and L1 = `1 , we compute
(a)

Pk = H (L|L1 = `1 , T = t) = log (|L(t, `1 )|)
!
t−k−1
Y 2m − 2k+` mt
(b)
≈ m(t − k),
= log
2t − 2k+`

(1)

`=0

where: (i) in (a) we let L(t, `1 ) represent the set of subspaces
Lt ⊂ Fm
2 of dimension t such that `1 ⊂ Lt ; moreover, the
equality follows by assuming that the underlying system maintains a uniform distribution across all feasible t-dimensional
subspaces of Fm
2 ; (ii) the equality in (b) follows by standard
counting arguments used to characterize the number of distinct
subspaces of a given dimension in a vector space. It is clear
that, when m  t, then Pk in (1) decreases linearly with k,
i.e., the less rows of the coding matrix c1 learns, the less it

can infer about the subspace spanned by the T rows of the
coding matrix A. This suggests that, by increasing k, c1 has
more uncertainty about qi . It is also clear that Pk in (1) is
zero when k = t; this is because, under this condition, c1
receives the entire index coding matrix and hence it will be
able to perfectly reconstruct the subspace spanned by its rows.
However, although Pk in (1) is zero when k = t, c1 might still
have uncertainty about qi [1]. Quantifying this uncertainty is
an interesting open problem that does not appear to be an
easy task; this uncertainty, in fact, depends on the underlying
system, e.g., on the index code used by the server and on the
distribution with which the index coding matrix is selected.
We now build on the analysis above – that shows the benefits
of limiting the access of the clients to the coding matrix –
and focus on finding conditions that guarantee that P can be
constructed while ensuring that each client ci , i ∈ [n], successfully decodes its request bqi using at most k transmissions.
Towards this end, we derive upper and lower bounds on Tk .
In particular, our main result is stated in the theorem below.
FT2 ×m

Theorem III.1. Given an index coding matrix A ∈
with T ≥ 2, it is possible to transform it into Ak = PA with
P ∈ FT2 k ×T , such that each client can recover its request by
combining at most k rows of it, if and only if
)
(

k 
X
Tk
?
≥n .
(2)
Tk ≥ T = min Tk :
i
i=1
Moreover, there exist constructions of P such that:
• When dT /2e ≤ k < T , then
Tk ≤ min {n, T + 1} ;
•

(3)

When 1 ≤ k < dT /2e, then
Tk ≤ min {n, Tub } ,

(4)

where

T
if k = 1

 2
T
−1
e
d
if Tlast = 1
2(2k + 1) 2k−1
Tub =

T

−1
d
e
2k−1
(Tlast +2) otherwise
(2k + 1)
O( T
log
k
)
=2 k
if k 6= 1,
l
m

T
−1 .
where Tlast = T − (2k − 1) 2k−1

(5)

We provide the proof of the lower bound in (2) in the
Appendix, while in Section IV we give explicit constructions
for P for the two regimes in Theorem III.1, hence proving the
upper bounds on Tk in (3) and (4). The results in Theorem III.1
also imply the following lemma (see also the Appendix).
Lemma III.2. Consider the regime n = 2T − 1. We have
• When dT /2e ≤ k < T , the bounds in (2) and (3)
coincide, i.e., the provided construction of P is optimal;
• When 1 ≤ k < dT /2e, then the bound in (2) becomes

1/k
T
k 2T − 1
k−1
Tk ≥
= 2Ω( k +α log k) , α =
. (6)
e
k
k

We now conclude this section with some comparisons
between the lower and upper bounds on Tk for the case
n = 2T − 1. According to Lemma III.2, a construction of
P with Tk = T + 1 (provided in Section IV) is optimal
for k ≥ dT /2e. In other words, by adding only one more
transmission to the original index code, clients need at most
half of the transmissions to recover their request; this enhances
the attained level of privacy. Differently, for 1 ≤ k < dT /2e,
the orders of the lower bound in (6) and upper bound in (4)
are different. This implies that the construction of P for this
regime (see Section IV for the details) is not optimal. However,
we show next that there exist some regimes of k where the
two bounds are close in order. In particular,
• k is constant. In this case, we have Tk = 2Θ(T ) , i.e., the
upper and lower bounds have the same order in the exponent.
• k = T /c where c > 1 is constant. In this case, we have
Tk = 2Θ(log T ) , i.e., this represents another regime where the
upper and lower bounds have the same order in the exponent.
IV. C ONSTRUCTIONS OF k-L IMITED -ACCESS S CHEMES
In this section, we give explicit constructions of the P
matrix and prove the two upper bounds on Tk in (3) and (4).
Our design of P allows to reconstruct any of the 2T vectors
of size T . Recall that A is full rank and that the i-th row
of G can be expressed as gi = di A, where di ∈ FT2 is the
coefficients row vector associated with gi .
Case I: dT /2e ≤ k < T . When n ≥ T + 1, let
 
I
P= T ,
(7)
1T
which results in a matrix Ak with Tk = T + 1, matching the
bound in (3). We now show that each gi = di A, i ∈ [n], can
be reconstructed by combining up to k vectors of Ak . Let
w(di ) be the Hamming weight of di . If w(di ) ≤ dT /2e, then
we can reconstruct gi as gi = [di 0]Ak , which involves adding
w(di ) ≤ dT /2e ≤ k rows of Ak . Differently, if w(di ) ≥
dT /2e+1, then we can reconstruct gi as gi = [d̄i 1]Ak , where
d̄i is the bitwise complement of di . In this case, reconstructing
gi involves adding T − w(di ) + 1 ≤ bT /2c ≤ k rows of Ak .
When n < T + 1, then it is sufficient to send n uncoded
transmissions, where the i-th transmission satisfies ci , i ∈ [n].
In this case ci has access only to the i-th transmission, i.e.,
k = 1. This completes the proof of the upper bound in (3).
Case II: 1 ≤ k < dT /2e. First, we consider n ≥ Tub , where
Tub is defined in (5). For this, we provide a construction for
P that is based on multiple uses
m construction in Case I.
l of the
T
In what follows, we let Tc = 2k−1 . Consider the following
sets of distinct vectors (i.e., by omitting replicated vectors)

Pj = 02k−1 , 12k−1 , e2k−1
; ∀i ∈ [2k−1] , j ∈ [Tc −1] , (8a)
i
n
o
PTc = 0Tlast , 1Tlast , eTi last ; ∀i ∈ [Tlast ] ,
(8b)
where Tlast = T − (2k − 1)(Tc − 1). Then, our construction of
P is based on different concatenations of various elements of
the above sets as we explain in what follows. Let
P = P1 × P 2 × . . . × P T c

0
0
0
0
0
P=

0
0
0
0
0
b

0
0
0
0
0

0
0
0
0
1

b

0
0
0
0

0
0
0
0

0
0
0
0
1
b

0
0
0
0
1

0
1
1
0
0

1
1
1
1

0
1
1
0

b
b

1
1
1
1

0
0
0
0

0
0
0
0

b

0
1
0
1
0
0
1
0
1

Figure 1. Construction of P for T = 8 and k = 2.

be the Cartesian product of the sets defined in (8) and P(i), i ∈
[Tk ], be the i-th tuple of P. Then, the i-th row vector pi of
P is constructed by concatenating the elements of the tuple
P(i) in their respective order (i.e., the first element of P(i)
is the left-most part of pi , the second element of P(i) is the
second left-most part of pi and so on). It is not difficult to see
that with this construction pi has length T . Since from (8) we
have that, for j ∈ [Tc − 1],


2
k=1
2
Tlast = 1
|Pj | =
|PTc | =
,
2k + 1 k > 1
Tlast + 2 Tlast > 1
QTc
then we have j=1
|Pj | possible different ways of concatenating vectors from these sets. This gives the bound in (4). To
illustrate this process consider the following example.
Example. Let T = 8 and k = 2 for which Tc = 3 and Tlast = 2.
Then, we have

 
 

P1 = P2 = 0 0 0 , 1 1 1 , 1 0 0 ,

 

0 1 0 , 0 0 1 ,

 
 
 

P3 = 0 0 , 1 1 , 1 0 , 0 1 .
Figure 1 shows how P is then constructed.
We now need to prove that any gi , i ∈ [n], can be
reconstructed using at most k rows of Ak . Notice that this
is equivalent to showing that we need at most k rows of P
to reconstruct di , i ∈ [n]. This is because, if this holds, then
di = d?i P where the row vector d?i ∈ FT2 k has at most k nonzero elements. Then, this would imply gi = di A = d?i PA =
d?i Ak , i.e., gi is reconstructed by using at most k rows of Ak .
In what follows, we therefore prove that any di , i ∈ [n], can
be reconstructed by using at most k rows of P. As a running
example to illustrate the different
 steps of our proof we use

the case in Figure 1 with di = 1 1 0 0 1 0 0 0 .
Step 1. Starting from the left-most bit, we split di , i ∈ [n],
into (Tc − 1) parts of length (2k − 1) and one last part of
length Tlast . We denote by di (j) the j-th part with j ∈ [Tc ].
Running example. We have






di (1) = 1 1 0 , di (2) = 0 1 0 , di (3) = 0 0 .
Step 2. We leverage our proof of Case I, where we showed
that P in (7) can be used to reconstruct any vector of length T
using dT /2e ≤ k < T rows. This, in fact, implies that: (i) any
di (j), j ∈ [Tc − 1], can be reconstructed by adding at most

k elements of Pj (excluding the first element), and (ii) any
di (Tc ) can be reconstructed by adding at most k elements of
PTc (excluding the first element). We let Rj , j ∈ [Tc ], be the
set of elements of Pj needed to reconstruct di (j). Clearly,
|Rj | ≤ k, j ∈ [Tc ]. Let R? = maxj∈[Tc ] |Rj |. Then, we
further populate Rj , j ∈ [Tc ] with R? − |Rj | zero vectors,
so that all Rj have the same cardinality.
Running example. We have R? = 2 and

 

R1 = 1 0 0 , 0 1 0 ,

 

R2 = 0 1 0 , 0 0 0 ,

 

R3 = 0 0 , 0 0 .
Step 3. We concatenate the different elements of Rj , j ∈ [Tc ].
In particular, for each ` ∈ [R? ] we create a vector of length
T by concatenating the elements in the `-th position of all
Rj , j ∈ [Tc ], as follows: we put the `-th element of R1 as the
left-most part, then we concatenate to it the `-th element of R2
and so on until RTc . Thus, we obtain a set R? of R? vectors
of length T . Clearly, from our construction of P, each element
of R? is a row of P. Moreover, from our construction in the
previous step of Rj , j ∈ [Tc ], we have that the sum of the R?
vectors in Rj reconstructs di (j). Hence, it is not difficult to
see that the sum of the R? elements of R? reconstructs di .
Running example. We have


R? = 1 0 0 0 1 0 0 0 ,


0 1 0 0 0 0 0 0 .
By
adding the two elements
of R? we obtain


1 1 0 0 1 0 0 0 , which is precisely the di
we wanted to reconstruct.
When n < Tub , then it is sufficient to send n uncoded
transmissions, where the i-th transmission satisfies ci , i ∈ [n].
In this case ci has access only to the i-th transmission, i.e.,
k = 1. This completes the proof of the upper bound in (4).
V. R ELATED W ORK
The problem of protecting privacy was initially proposed
to enable the disclosure of databases for public access, while
maintaining the anonymity of the users [6]. Similar concerns
have been raised in the context of Private Information Retrieval (PIR), which was introduced in [7] and has received
a fair amount of attention [8], [9]. In particular, in PIR the
goal is to ensure that no information about clients’ requests
is revealed to a set of malicious databases when clients
are trying to retrieve information from them. Similarly, the
problem of Oblivious Transfer (OT) was studied [10], [11]
to establish, by means of cryptographic techniques, two-way
private connections between the clients and the server.
We were here interested in addressing privacy concerns in
broadcast domains. In particular, we analyzed this problem
within the index coding framework, as we recently proposed
in [1]. This problem differs from secure index coding [12],
where the goal is to guarantee that each client does not learn
any information about the content of the messages other than
its request. Differently, our goal was to limit the information

that a client can learn about the identities of the requests of
other clients. Moreover, our approach here has a significant
difference with respect to [1]. In fact, while in [1] our goal
was to design the encoding matrix to guarantee a high-level
of privacy, here we assumed that an index coding matrix (that
satisfies all clients) is given to us and we developed methods
to increase its achieved levels of privacy.
The solution that we here proposed to limit the privacy
leakage is based on finding overcomplete bases. This approach
is closely related to compressed sensing and dictionary learning [13], where the goal is to learn a dictionary of signals such
that other signals can be sparsely and accurately represented
using atoms from this dictionary. These problems seek lossy
solutions, i.e., signal reconstruction is not necessarily perfect.
This allows a convex optimization formulation of the problem,
which can be solved efficiently [14]. In contrast, our problem
was concerned with lossless reconstructions, in which case the
optimization problem is no longer convex.
VI. C ONCLUSION
We studied an index coding problem, where clients are
eager to learn the identity of the request of other clients.
We proposed the use of k-limited-access schemes to mitigate
the privacy risks, which provide clients with only part of
the coding matrix and still ensure that they can all recover
their requested message. We showed that such approach can
achieve higher levels of privacy than conventional schemes
(where the entire matrix is broadcast to all users) at the cost of
additional number of transmissions. This analysis sheds light
on an inherent tradeoff between bandwidth savings and privacy
protection in broadcast domains. Future work would include
the derivation of tighter upper and lower bounds on the number
of transmissions required by a k-limited-access scheme.
A PPENDIX
In order to prove the lower bound in (2), we establish a
connection between our problem and a linear-algebraic one,
namely the problem of representing vectors in finite vector
spaces. Given a matrix A, denote by VA ⊆ FT2 the subspace
formed by the span of the rows of A. It is clear that the
dimension of VA is at most T (exactly T if A is full rank) and
that the n distinct rows of G lie in VA . Let ai ∈ Fm
2 , i ∈ [Tk ],
be the i-th row of Ak . Then this problem is equivalent to the
following: what is a minimum-size set of vectors Ak = {a[Tk ] }
such that any row vector of G can be represented by a linear
combination of at most k vectors of Ak ?
A lower bound on Tk can be obtained as follows. Given
Ak , there must exist a linear combination of at most k vectors
of Ak that is equal to each of the n distinct row vectors of G.
The number of distinct non-zero linear combinations of up to
k

P
Tk
k vectors is at most equal to
j . Thus, we have
j=1


k 
X
Tk
i=1

i

≥ n,

(9)

which gives precisely the bound in (2).
We now derive the lower bounds in Lemma III.2, i.e., we
evaluate (2) for n = 2T − 1. From (9), we obtain

k 
X
Tk
≥ 2T − 1.
(10)
i
i=1
Since in general Tk ≥ T , to prove that Tk ≥ T + 1 for k < T ,
it is sufficient to show that we have a contradiction for Tk = T .
Indeed, by setting Tk = T , the bound in (10) becomes
k  
T  
X
X
T
T
≥ 2T − 1 =
,
i
i
i=1
i=1
which clearly is not possible since k < T . Hence, Tk ≥ T + 1
for all k < T . However, for 1 ≤ k < dT /2e, we can refine
this lower bound as follows
  X
k


k 
Tk
Tk
Tk e
≥k
≥
≥ 2T − 1
k
k
k
i
i=1
 T
1/k
k 2 −1
.
=⇒ Tk ≥
e
k
This concludes the proof of the lower bounds in Lemma III.2.
R EFERENCES
[1] M. Karmoose, L. Song, M. Cardone, and C. Fragouli, “Private broadcasting: an index coding approach,” to appear in IEEE International
Symposium on Information Theory (ISIT), June 2017.
[2] Z. Bar-Yossef, Y. Birk, T. Jayram, and T. Kol, “Index coding with side
information,” IEEE Transactions on Information Theory, vol. 57, no. 3,
pp. 1479–1494, February 2011.
[3] H. Esfahanizadeh, F. Lahouti, and B. Hassibi, “A matrix completion
approach to linear index coding problem,” in IEEE Information Theory
Workshop (ITW), November 2014, pp. 531–535.
[4] X. Huang and S. El Rouayheb, “Index coding and network coding via
rank minimization,” in IEEE Information Theory Workshop-Fall (ITW),
October 2015, pp. 14–18.
[5] M. A. R. Chaudhry and A. Sprintson, “Efficient algorithms for index
coding,” in INFOCOM Workshops 2008, IEEE, April 2008, pp. 1–4.
[6] C. C. Aggarwal and S. Y. Philip, “A general survey of privacy-preserving
data mining models and algorithms,” in Privacy-preserving data mining.
Springer, 2008, pp. 11–52.
[7] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” Journal of the ACM (JACM), vol. 45, no. 6, pp. 965–981,
November 1998.
[8] R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpuk, “Private
information retrieval from coded databases with colluding servers,”
arXiv:1611.02062, November 2016.
[9] K. Banawan and S. Ulukus, “The capacity of private information
retrieval from coded databases,” arXiv:1609.08138, September 2016.
[10] G. Brassard, C. Crepeau, and J.-M. Robert, “All-or-nothing disclosure of
secrets,” Advances in Cryptology: Proceedings of Crypto ’86, SpringerVerlag, pp. 234–238, 1987.
[11] M. Mishra, B. K. Dey, V. M. Prabhakaran, and S. Diggavi, “The
oblivious transfer capacity of the wiretapped binary erasure channel,”
in IEEE International Symposium on Information Theory, June 2014,
pp. 1539–1543.
[12] S. H. Dau, V. Skachek, and Y. M. Chee, “On the security of index coding
with side information,” IEEE Transactions on Information Theory,
vol. 58, no. 6, pp. 3975–3988, June 2012.
[13] G. Chen and D. Needell, “Compressed sensing and dictionary learning,”
Finite Frame Theory: A Complete Introduction to Overcompleteness,
vol. 73, p. 201, 2016.
[14] R. Rubinstein, A. M. Bruckstein, and M. Elad, “Dictionaries for sparse
representation modeling,” Proceedings of the IEEE, vol. 98, no. 6, pp.
1045–1057, June 2010.

