1

Secure Multi-Source Multicast

arXiv:1702.03012v2 [] 22 Nov 2017

Alejandro Cohen
BGU

Asaf Cohen
BGU

Abstract—The principal mission of Multi-Source Multicast
(MSM) is to disseminate all messages from all sources in a
network to all destinations. MSM is utilized in numerous applications. In many of them, securing the messages disseminated
is critical.
A common secure model is to consider a network where there
is an eavesdropper which is able to observe a subset of the
network links, and seek a code which keeps the eavesdropper
ignorant regarding all the messages. While this is solved when all
messages are located at a single source, Secure MSM (SMSM) is
an open problem, and the rates required are hard to characterize
in general.
In this paper, we consider Individual Security, which promises
that the eavesdropper has zero mutual information with each
message individually. We completely characterize the rate region
for SMSM under individual security, and show that such a
security level is achievable at the full capacity of the network, that
is, the cut-set bound is the matching converse, similar to nonsecure MSM. Moreover, we show that the field size is similar
to non-secure MSM and does not have to be larger due to the
security constraint.

Muriel Médard
MIT

Omer Gurewitz
BGU

Figure 1: Secure multi-source multicast with LNC, for two
sources si , with two messages each and four legitimate destination nodes di . The eavesdropper min-cut is at most 1. The
edges in the graph point downward.

I. I NTRODUCTION
Linear Network Coding (LNC) [1] and Random Linear Network Coding (RLNC) [2] are essential for efficient utilization
of network resources. With network coding, multiple sources
can multicast information to all destinations simultaneously,
at rates up to the min-cut between the sources and the
destinations. Figure 1 depicts a simple example: the mincut from any source to any destination is 2, and from both
sources to any destination is 4, hence one can disseminate
2 messages from each source to all destinations. However, in
many practical multicast applications, it is important to ensure
privacy is not compromised if an eavesdropper (Eve) is present
in the network. Indeed, the theory of secure network coding
is vast. We include here only the most relevant works.
When the sources are co-located at a single node, several
secure network coding solutions were suggested [3]–[8]. Such
solutions guarantee the mutual information between Eve’s
data, Z, and all the messages is 0. For example, returning
to Figure 1, if only source s1 had messages to send, and
Eve would be able to wiretap one link in the network, then
secure network coding would guarantee secure dissemination
of one message from the source to all destinations. This is a
reduction in rate compared to the full capacity, as the min-cut
from s1 to any destination is 2. However, when requiring zero
mutual information with all messages from the source, this
rate reduction is essential, and matches the converse result.
A.Cohen, A,Cohen and O. Gurewitz are with the Department of Communication Systems Engineering, Ben-Gurion University of the Negev, BeerSheva 84105, Israel (e-mail: alejandr@post.bgu.ac.il; coasaf@post.bgu.ac.il;
gurewitz@post.bgu.ac.il). M.Médard is with the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology
(medard@mit.edu). Parts of this work appeared at the IEEE International
Symposium on Information Theory (ISIT), 2017.

When the network includes multiple sources which are not
co-located, the problem is more involved. Clearly, applying a
single-source, secure network coding solution at each source
would give an achievable scheme. In the example, if Eve
wiretaps one link, one can clearly multicast one message from
each source, to all destinations. This solution, however, may
be wasteful, as it is half of the full capacity of the network,
“wasting” one message per source, although Eve may capture
only a single link regardless of the number of sources. Indeed,
there is no matching converse result for the above solution.
In [9], [10], the authors gave a necessary and sufficient condition for Secure Multi-Source Multicast (SMSM). However, it
is a condition on ranks of matrices having the global encoding
vectors as columns, and, unlike non-secure MSM or secure
single-source multicast, it does not translate directly to rate
or min-cut constraints. Thus, the problem of determining the
rate region in SMSM is an open problem in general [11], and
as mentioned in [12, Section VI], seeking models for which it
is solvable is important. In [13], the authors characterized the
network coding capacity of several models, including SMSM,
via the entropic region Γ∗ . Yet, to date, this region is not fully
characterized.
Main Contribution
In this paper, we consider SMSM under an Individual
Security constraint. In this model, the eavesdropper is kept
ignorant, in the sense of having zero mutual information,
regarding each message separately, yet may potentially obtain
insignificant information about mixtures of packets transmitted. Such a security model was recently used in various

2

canonical problems, e.g., wiretap channels [14], more general
broadcast channels [15]–[18] and multiple-access channels
[19], [20], and, although not specifically mentioned as such,
is also related to weakly secure network coding [21] and the
notion of algebraic security [22], [23], which consider the
information in linear combinations of messages.
We completely characterize the rate region for individually
secure MSM. Specifically, we show that secure communication
is achievable up to the min-cut, that is, without any decrease
in the rate or any message “blow-up” by extra randomness. In
fact, due to the individual security constraint, messages protect
one another, and in the context of Figure 1, one is able to send
two messages from each source securely, although Eve may
observe any single link.
We then turn to a few applications where the suggested coding scheme ca be useful. Specifically, we consider data centers,
wireless networks and live broadcasting of video using multipath streaming, and show how the individual security coding
schemes suggested in this paper is applicable, achieving the
full capacity of those systems. Finally, we show that the coding
scheme is applicable to algebraic gossip as well [24], resulting
in secure gossip without extra rounds. For example, consider
the ”Random Phone Call” model. This model was introduced
in [25] as special case of uniform gossip. In each round
of communication, every participant may ”call” a random
participant, and send one unit of information. The goal is,
of coarse, to disseminate messages from the source to all
participants. Rigorously, the underlying graph is complete and
unweighted. A detailed analysis of this model is given in [26],
[27]. It was shown that in a random phone call model with v
nodes, the flooding time is Θ(log v), with constant throughput.
Of coarse this is without any secrecy constraint. Any phone
call which Eve listens to contains relevant information, and
results in leakage. Using the code suggested in this paper, we
will show that one can design a secure gossip scheme, which
make sure that as long as Eve dose not listen to too many
calls, she remains complectly ignorant regarding any specific
message, and all this without any loss in throughput or number
of rounds.
The structure of this paper is as follows. In Section II,
a SMSM model is formally described. Section III includes
our main results, with the individually-SMSM direct proved
in Section IV and converse proved in Section V. In Section VI, we show a few important examples, foe which the
individual security coding is applicable. Section VII includes
a linear code construction for the individually-SMSM model.
Section VIII describes a Strongly-SMSM algorithm and proves
a direct result for it. Section IX concludes the paper.
II. M ODEL AND P ROBLEM F ORMULATION
SMSM is specified by a graph G = (V, E), where V and
E are the node set and the edge set, respectively. We assume
noise-free links of unit capacity. This capacity can be thought
of as one ”packet” of c bits, plus some negligible overhead.1
1 As in most LNC solutions, a header is required for each message. Thus,
we assume messages of length c, large enough to make the overhead in the
header negligible.

The node set V contains a subset of source nodes S =
{S1 , . . . S|S| } and a subset of legitimate destination nodes
D = {D1 , . . . D|D| }. Each of the sources has its own set of k
independent messages of length c each, over the binary field.
We denote them by a messages matrix
~ s,1 ; M
~ s,2 ; . . . ; M
~ s,k ] ∈ {0, 1}k×c ,
Ms = [M
~ s,j , j ∈
where each row corresponds to a separate message M
{1, . . . , k}.
We assume an eavesdropper which can obtain a subset of
w packets traversing the network. Specifically, we define the
eavesdropper matrix as
c
Zw = [Z1c ; Z2c ; . . . ; Zw
] ∈ {0, 1}w×c .

We denote the values of min-cuts in the network by ρ(.; .).
For example, for s1 ∈ S and d1 ∈ D, ρ(s1 ; d1 ) represents the
value of the min-cut from source node s1 to legitimate node
d1 . ρ(s1 ; z) represents the value of the min-cut from source
node s1 to the eavesdropper (assuming z is a virtual node
with infinite capacity from the w edges observed by Eve) and
ρ(S; d1 ) represents the value of the min-cut from all the source
nodes to legitimate node d1 .
The goal is to design secure multi-source multicast coding
scheme where legitimate nodes send their available messages
in order to disseminate all the messages to all the legitimate destination nodes, yet, observing w packets from the
communication between legitimate nodes, the eavesdropper is
ignorant regarding the messages.
Definition 1. An MSM algorithm with parameters k and w is
Reliable and Individually or Strongly secure if:
(1) Reliable: At the legitimate destination node d ∈ D,
letting Yd denote the message matrix obtained, for any set
of messages Ms , s ∈ S, we have
P (M̂s (Yd ) 6= Ms ) ≤ ,
where M̂s (Yd ) is the estimation of messages Ms at d.
(2) Individually secure: At the eavesdropper, observing w
packets, we have
H(Ms,j |Zw ) = H(Ms,j ),
for all j ∈ {1, . . . , k} and for all s ∈ S.
(3) Strongly secure: At the eavesdropper, observing w packets,
for all s ∈ S we have
H(Ms |Zw ) = H(Ms ).
Remark 1. The individual-secrecy constraint given in Definition 1.2 does not promise perfect, strong-secrecy [5], [8],
[9], which is, having the mutual information with all messages negligible. Individual-secrecy ensures secrecy only on
each message Ms,j separately. The eavesdropper, observing
Zw , may obtain some information on the combination of
k messages since the messages are not independent given
Zw . However, since the k original messages are mutually
independent, the leaked information has no meaning [14]–[20],
[28]. In other words, since

3

I(Ms ; Zw ) =

X

I(Ms,k ; Zw |Msk−1 ) ≥

k

X

I(Ms,k ; Zw ),

k

we require that the r.h.s will be small, however, this does not
guarantee that the l.h.s is small. If the eavesdropper receives
message Ms,j by any other manner than the Individual-SMSM
transmissions, Eve may obtain some information on other
messages Ms,i , i 6= j, from Ms,j and Zw . If it is required to
prevent the possibility of such an attack, one can get perfect
secrecy using Definition 1.3, yet at the price of a lower rate,
as given in Section VIII.
Remark 2. For multicast problems and LNC, the condition in
(1) can be used with  = 0 [1], [2]. Yet, we allow a small
error to cope with protocols such as randomized gossip [24],
[29], which we discuss later in this paper.
Remark 3. The first code construction we consider, given in
Section IV, is based on random coding. Therefore, in that case,
the individual secrecy constraint will hold only asymptotically,
that is, H(Ms,j |Zw )/H(Ms,j ) → 1 as k grows. Then, in
Section VII, we suggest a structured linear code, which results
in zero mutual information, such that there is no requirement
for k to grow.
A. Source and Network Coding
We assume a source s ∈ S may use an encoder,
f : Ms → Xs ∈ {0, 1}n×c ,
which maps each message matrix Ms to a matrix Xs of
codewords. When using a strong security constraints, e.g.,
[5], [8], n > k and this represents a message “blow-up”
using a random key, used to confuse Eve. However, the main
contribution herein, is that under individual-secrecy, n = k
suffices, and there will be no rate loss due to the secrecy
constraint.
~ transmitted are linear combinaThen, the source packets Y
n
~
tions of {Xr }r=1 with coefficients in the usual LNC sense,
i.e.,
n
X
~
~ r.
Y =
µr X
r=1

Each node maintains a subspace Yv that is the span of all
packets known to it. In RLNC, when node v sends a packet,
~ ), it chooses uniformly a packet from Yv by taking
Out(Y
a random linear combination. If a deterministic algorithm is
used, e.g., [30], the coefficients are calculated based on the
network topology. The code we suggest herein is only at the
sources, and then utilizes any capacity-achieving, non-secure
network code.

well as any legitimate node which has messages it previously
received, pick a random node to exchange information with.
The information exchange is done by either sending (PUSH) or
receiving (PULL) a message. In algebraic gossip, the message
sent by a node v is simply a random linear combination of the
vectors which form a basis for Yv . The process stops when
all the legitimate nodes have all the messages, i.e., have a
full rank matrix. We briefly review the definitions and results
from [29] for non-secure gossip networks, which we will use
to formulate our result in this context.
Definition 2. A network is oblivious if the topology of the
network, Gt at time t, only depends on t, G0t for any t0 < t
and some randomness. We call an oblivious network model
furthermore i.i.d., if the topology Gt is independent of t and
prior topologies.
The importance of Definition 2 lies in the fact that the
topology of an oblivious network may change in time, but only
based on the past topology and some external randomness.
Topology dose not change based on the data traversing the
network. Consider a single (uncoded) message, and the set
of nodes Sl which received that message after l rounds. Sl
advances like a flooding process F . That is, Sl ⊆ Sl0 ⊆ V for
l ≤ l0 , with an absorbing sate V. We say that F stops at time
t if the message is received at all nodes after t rounds. Let
SF be the random variable denoting the stopping time of F .
Definition 3. We say an oblivious network with a vertex set
V floods in time T with throughput α if there exists a prime
power q such that for every vertex v ∈ V and every k > 0 we
have P [SF ≥ T + k] < q −αk .
III. M AIN R ESULTS
The three main results in this paper completely characterize
the rate region for individually secure multi-source multicast.
Specifically, we give tight achievability and converse, and a
tight characterization of the number of rounds required under
a gossip model. Thus, the first main result is the following
achievability theorem, which states that individually-secure
multi-source multicast is achievable at rates up to the network
min-cuts, using LNC.
A. Individually Secure MSM

B. Gossip in Oblivious Networks

Theorem 1. Assume an SMSM network (V, E, S, D, w). There
exists a coding scheme which disseminates k messages from
each source in S, to all destinations in D, while keeping an
eavesdropper which observes w links ignorant with respect to
each message individually if:
1) For all s ∈ S and all d ∈ D, ρ(s, d) ≥ k.
2) For all d ∈ D, ρ(S, d) ≥ k|S|.

While the results in this paper are tailored to LNC in the
sense of [1], [2], they easily apply to algebraic gossip [24] as
well. Such algebraic gossip protocol have been considered in
the literature for many tasks, such as ensuring database consistency, computing aggregate information and other functions of
the data [25], [31]–[33]. We briefly describe this model. The
network operates in rounds. In each round t, the sources, as

Under strong-secrecy, i.e., requiring Eve’s mutual information with all messages simultaneously to be zero, the problem
of MSM is still open [11], [12, Section VI]. Clearly, if Eve
observes w links, a naive implementation, which increases the
message rates from each source by w, can send k messages
from each source and achieve strong secrecy if:
1) For all s ∈ S and all d ∈ D, ρ(s, d) ≥ k + w.

4

2) For all d ∈ D, ρ(S, d) ≥ (k + w)|S|.
However, such an implementation is clearly wasteful, and, to
date, the optimal strategy is unknown. Obviously, the required
rates under strong secrecy are higher than the min-cut bound,
as even for single-source multicast one needs ρ(s1 , di ) ≥ k+w
[5]. The importance of Theorem 1 is that under individual
secrecy, not only the rate region can be characterized, and
is achievable using linear network coding, individually secure
MSM is possible up to the min-cuts in the network.
In Section VIII, we provide a code for Strong-SMSM. It
is important to note that in the code suggested, the alphabet
size dose not increase with the network parameters due to the
strong-security constraint.
The tightness of Theorem 1, in terms of rates, is trivially
achieved using the cut-set bound. That is, the conditions
ρ(s, d) ≥ k and ρ(S, d) ≥ k|S| are required solely to
achieve reliability, nevertheless when security is an additional
constraint. However, a stronger notion of a converse can
be given. To this end, we first note that while Theorem 1
guarantees individual secrecy according Definition 1, it still
gives a slightly weaker level of security than is possible at the
same rates. Specifically, Theorem 1 guarantees I(Ms,j ; Z) = 0
for any single message j. However, ensuring the mapping from
Ms to Xs mixes the messages appropriately, i.e., satisfies rank
constraints similar to [12, Lemma 3.1], can, in fact, ensure Eve
is kept ignorant of any set of k−w messages. That is, guarantee
ks -individual secrecy with respect to any set of ks ≤ k − w
denote a set of k − w messages from
messages. Let Mk−w
s
denote
the
remaining w. Thus, we also have the
s, and Mw
s
following corollary.
Corollary 1. Assume an SMSM network (V, E, S, D, w).
There exists a coding scheme which disseminates k messages
from each source in S, to all destinations in D, while keeping
an eavesdropper which observes w links ignorant with respect
to any set of ks ≤ k − w messages individually, such that
I(Mk−w
; Zw ) = 0, if:
s
1) For all s ∈ S and all d ∈ D, ρ(s, d) ≥ k.
2) For all d ∈ D, ρ(S, d) ≥ k|S|.
In Section IV-B, we prove the ks -individual secrecy constraint is indeed met.
Under such an individual secrecy constraint, the converse
below gives a stronger result than the min-cut bound.
Theorem 2. Assume an SMSM network (V, E, S, D, w). Under individual security for k − w messages, that is, requiring
I(Mk−w
; Zw ) = 0 for any set of k − w messages, one must
s
have
H(Ms ) ≤ ρ(s, di ) − ρ(s, z) + w.
This result should be interpreted as follows. If Eve observes
w independent links, and ρ(s; z) = w, then one must have
H(Ms ) ≤ ρ(s, di ), which is the cut set bound. Of coarse,
as mentioned before, the surprising part is that this bound is
tight, hence such a level of security is available without any
loss in rate. However, if Eve observes more then w links,
and one wishes to maintain the individual-secrecy constraint,
then H(Ms ) should be strictly smaller than ρ(s, di ) and at

the same amount. E.g., if Eve observes w + e links, we have
H(Ms ) ≤ ρ(s, di ) − e. This means a linear increase in Eve’s
power results in a linear decrease in rate.
Finally, it is important to note that the constraint on how
many messages Eve catches is set on the entire network, thus,
Eve may catch w messages of a single source, or w messages
from several sources all together. Secrecy is maintained in any
case, as under individual secrecy, messages from other sources
can only increase secrecy, and any network code cannot create
linear combinations with other messages which reduce the
secrecy level. This is another benefit of the model, and hence
the network code can be any LNC, without an increase in
alphabet size.
B. Algebraic Gossip
As mentioned earlier, the suggested code easily applies to
algebraic gossip as well, since this can be viewed as linear
network coding over a time-extended graph. The following
results capture the number of rounds required to (individually)
securely disseminate k messages from each of the |S| sources
to all nodes in the network.
Theorem 3. Assume an oblivious network that floods in time
T with throughput α. Then, for |S| nodes in the network with
k messages each, algebraic gossip spreads the k|S| messages
to all nodes with probability 1 −  after
1
T 0 = T + (k|S| + log −1 )
α
rounds, while keeping any eavesdropper which observes at
most w ≤ k − ks packets, ignorant with respect to any set of
ks messages individually.
Thus, compared to only a reliability constraint, the number
of rounds required for both reliability and individual-secrecy is
exactly the same as in the original non-secure gossip protocol.
Note that the result above is constant-optimal, as T is the
number of rounds required for a single message, hence one
cannot expect less that T 0 above for k|S| messages. This is
a perfect pipelining property [29], thus, surprisingly, one can
gossip securely messages to all parties in the network, without
any loss in rate and without any centralized mechanism for
routing, key exchange or any other encryption mechanism, as
long as the eavesdropper is interested in single messages.
C. Alphabet Size
Without secrecy constraints, Jaggi et al. proved that a field
with size greater than or equal to the number of destinations
is sufficient for multicast under LNC [30]. However, this may
not hold if it is required to keep an eavesdropper ignorant. Cai
et al. [5] devised a code which requires a field of exponential
sizeto obtain secrecy. There, the field size must be larger than
|E|
w . Feldman et al. [34] showed thatwthere exist networks
that require a field of size at least Θ(|E| 2 ). In [8], the authors
demonstrate that secure network coding can be considered as a
network generalization of the wiretap channel of type II. When
d is the number 3of2 destinations
in the multicast connection, a

2k d
field of size w−1+d
is sufficient, which is independent of |V |
and |E| but is still exponential in other network parameters.

5

bins is k, thus the codebook matrix is of the same size as Ms .
The codebook is depicted in Figure 2.
2) Source and legitimate Node encodings: At the s-th
source node, the encoder selects, for each column i of
bits Ms,1 (i); . . . ; Ms,k0 (i), one codeword, xk (e(i)), from
the bin indexed by Ms,1 (i); . . . ; Ms,k0 (i), where e(i) =
Ms,k0+1 (i); . . . ; Ms,k (i). That is, k 0 = k−w bits of the column
choose the bin, and the remaining w bits choose the codeword
within the bin.
Then, similar to many RLNC protocols, the sources transmit
linear combinations of the rows, with random coefficients.
Nodes transmit random linear combinations of the vectors
in Sv , which is maintained by each node according to the
messages received at the node.
A. Reliability
Figure 2: Binning and source encoding process for IndividualSMSM.
In the solution we suggest herein, the field size is determined only by the network coding scheme, that is, only by
the requirement for reliability, and is not increased by the
individual-security constraints. In the gossip case, for example,
since q −αk = 2−(α log q)k , any field size greater than or
equal to 2 will suffice, and an increase in the field size has
only a logarithmic effect on the throughput, meaning only a
logarithmic multiplier on the number of rounds T 0 required.
IV. C ODE C ONSTRUCTION AND A P ROOF
FOR I NDIVIDUAL -SMSM (T HEOREM 1 AND T HEOREM

3)

At each source node s ∈ {1, . . . , |S|}, we map each column
of the message matrix Ms to a column of the same length.
Specifically, as depicted in Figure 2, in the code construction phase, for each possible value for the partial column
Ms,1 (i); . . . ; Ms,k0 (i), 1 ≤ i ≤ c, of length k 0 = k − w in the
message matrix, we generate a bin, containing several columns
of length k. The number of columns in a bin corresponds to
w, the number of packets that the eavesdropper can wiretap,
in a relation that will be made formal in the sequel. Then, to
map the i-th column of the s-th message matrix, we select a
column from the bin corresponding to Ms,1 (i); . . . ; Ms,k0 (i).
The specific column within that bin is chosen according to
Ms,k0 +1 (i); . . . ; Ms,k (i). That is, the lower part of the original
column points to the bin, and the upper part of the original
column serves an index in order to choose the right column
from the bin. This way, a new, k × c message matrix Xs is
created. This message matrix contains k new messages of the
same size c. We may now turn to the detailed construction and
analysis.
1) Codebook Generation: Set ∆ = 2w+k . Q
Let P (x) ∼
k
Bernoulli(1/2). Using a distribution P (X k ) = j=1 P (xj ),
for each possible column M1 (i); . . . ; Mk0 (i) in the message
matrix, that is, 2k−w possibilities, generate ∆ independent and
identically distributed codewords xk (e), 1 ≤ e ≤ ∆, where 
can be chosen arbitrarily small. Thus, we have 2k−w bins,
each of size 2w+k . Note that the length of the columns in the

The reliability proof using RLNC is almost a direct consequence of [2]. Clearly, the min-cut is given by Theorem 1.
Hence, the legitimate nodes can easily reconstruct Xs for each
s (simple, non-secure, multi-source multicast). Then, each
destination maps Xs back to Ms , as this is a 1 : 1 mapping.
In the same way, using a gossip protocol, the reliability
proof is almost a direct consequence of [29, Theorem 1].
Hence, the number of rounds required is given by Theorem 3.
An example, obtaining both reliability and individual secrecy for two sources, with two messages each and four
legitimate destination nodes, where the eavesdropper mincut is at most 1, is given in Figure 1. Note that secure
communication with respect to one message is possible while
sending two messages from each source to all destinations.
B. Information Leakage at the Eavesdropper
We now prove the ks -individual security constraint is met,
; Zw ) → 0 for any set of ks ≤ k−w messages.
that is, I(Mk−w
s
In particular, for the individual constraint, we wish to show
that I(Ms,j ; Zw ) is small for all s ∈ S and all j. We will
do that by showing that given Zw , Eve’s information, all
possibilities for any set of ks ≤ k − w messages Mk−w
are
s
equally likely. Hence Eve has no intelligent estimation for
Mk−w
and Ms,j .
s
Denote by Ck the random codebook and by Xs the set
~ s,1 . . . M
~ s,k . To analyze the
of codewords corresponding to M
information leakage at the eavesdropper, note that Eve has
access to at most w linear combinations on the rows of Xs . We
will assume these linear combinations are in fact independent,
and since Eve has access to the coefficients, we will assume
Eve can even use Gaussian elimination and have access to w
rows from original matrix Xs .
Next, note that the columns of Xs are independent (by the
construction of the codebook, creating Xs is done independently per-column; c columns are used only to reduce the
NC overhead). Hence, it suffices to consider the information
leakage for each column i ∈ {1, . . . , c} from Xs separately.
For each column i of Ms , the encoder has ∆ independent
and identically distributed codewords, out of which one is
selected. Hence, there is an exponential number of codewords,

6

Due to the super exponential decay in k, when taking a union
bound over all columns, the probability that Eve decodes
correctly some column is small. Hence, by the chain rule for
entropies, since all the
Pc codewords in the codebook are independent H(Xs ) =
i=1 H(Xs (i)), for Eve, all codewords
are almost equiprobable and I(Mk−w
; Zw ) → 0. In particular,
s
I(Ms,j Zw ) → 0.
V. C ONVERSE (T HEOREM 2)

Figure 3: Codewords for Individual-SMSM algorithm lie exactly in a ball of radius l = k − w around Z.
from the eavesdropper’s perspective, that can generate a column in Xs , and we require that Eve is still confused even given
the w bit from each column. Let Zw (i) be the w bits Eve has
from column i. Denote l = k − w. Similar to the technique
used in [35] to prove that myopic adversaries are blind, we
define by Sh(Zw (i), l) the set of all k-tuples consistent with
Zw (i), i.e.,
k

k

Sh(Zw (i), l) = {b : b (SZ ) = Zw (i)},
where SZ denotes indices of the rows Eve has. Clearly, there
are 2l tuples in Sh(Zw (i), l). See Figure 3 for a graphical
illustration. We assume Eve has the codebook, yet does not
know which column from each bin is selected to be the
codeword. Hence, we wish to show that given Zw (i), Eve
will have at least one candidate per bin. The probability for a
codeword to fall in a given shell is
P r(Xks (i) ∈ Ck ∩ Xks (i) ∈ Sh(Zw (i), l))
Vol(Sh(Zw (i), l))
2(k−w)
=
.
k
2
2k
In each bin of Ck , we have ∆ = 2w+k codewords. Thus, the
number of codewords Eve sees on a shell, per bin is

In this section, we derive a converse result, which shows that
under individual secrecy on a group of k − w messages, not
only the rate is bounded by the min-cut, but, more importantly,
any independent link that Eve observes above w will require
to reduce the rate at the same amount in order to achieve both
reliability and secrecy.
Let Z̄ denote the random variable corresponding to the links
which are not available to Eve. Hence, Yd = (Z, Z̄). Let
Mk−w
denote a set of k − w messages, and Mw
s
s denote the remaining w. We will show that reliability, that is H(Ms |Yd ) =
; Z) = 0, imply that
0, and individual secrecy, that is, I(Mk−w
s
H(Ms ) is upper bounded by the term in Theorem 2.
H(Ms )
w
|Mw
= H(Mk−w
s ) + H(Ms )
s
(a)

k−w
≤ I(Mk−w
; Yd |Mw
|Yd ) + w
s
s ) + H(Ms

(b)

; Z, Z̄|Mw
≤ I(Mk−w
s)+w
s

k−w
; Z̄|Z, Mw
; Z|Mw
= I(Mk−w
s)+w
s ) + I(Ms
s
k−w
) − I(Z; Mw
; Z) + I(Mw
= I(Mk−w
s)
s ; Z|Ms
s

; Z̄|Z, Mw
+ I(Mk−w
s)+w
s
(c)

k−w
k−w
; Z̄|Z, Mw
) − I(Z; Mw
= I(Mw
s)+w
s ) + I(Ms
s ; Z|Ms

k−w
) − I(Z; Mw
= I(Mw
s)
s ; Z|Ms
k−w
, Z, Mw
+ H(Z̄|Z, Mw
s)+w
s ) − H(Z̄|Ms

=

2w+k ∗ 2k−w
= 2k .
|{m(i) : X (i) ∈ Sh(Z(i), l)}| =
2k
Hence, we can conclude that on average, and if k is not too
small, for every column in Ms Eve has a few possibilities
in each bin, hence cannot locate the right bin. However, it
is still important to show that all bins have (asymptotically)
equally likely number of candidate codewords, hence Eve
cannot locate a preferred bin.
To this end, we proved that the average number of codewords per column is 2k . We wish to show that now the
probability that the actual number of options deviates from
the average by more than ε is small. Define
k

EC1 (Z(i), l) := P r{(1 − ε)2k ≤
|m(i) : Xsk (i) ∈ Sh(Zw (i), l)| ≤ (1 + ε)2k }.
By the Chernoff bound, we have
0 k

P r(EC1 (Z(i), l)) ≥ 1 − 2−ε 2 .

w
k−w
) − I(Z; Mw
= I(Mw
s ) + H(Z̄|Z, Ms ) + w
s ; Z|Ms
k−w
k−w
) − H(Mw
) − H(Mw
= H(Mw
s)
s |Z, Ms
s |Ms
w
+ H(Mw
s |Z) + H(Z̄|Z, Ms ) + H(Z̄) − H(Z̄) + w
k−w
= I(Mw
|Z) − I(Z̄; Z, Mw
s ; Ms
s ) + H(Z̄) + w
k−w
= I(Mw
|Z) − I(Z̄; Mw
s ; Ms
s |Z) − I(Z̄; Z) + H(Z̄) + w
k−w
≤ I(Mw
|Z) − I(Z̄; Mw
s ; Ms
s |Z) + H(Z̄) + w
w
k−w
= H(Mw
) − H(Mw
s |Z) − H(Ms |Z, Ms
s |Z)

+ H(Mw
s |Z, Z̄) + H(Z̄) + w
≤ H(Z̄) + w
(d)

≤ ρ(si ; di ) − ρ(si ; z) + w,
where (a) is since conditioning reduces entropy, (b) is due to
the reliability constraint, (c) follows since we assume that Eve
is kept ignorant regarding any group of w −k messages, hence
I(Mk−w
; Z) = 0, and (d) follows since ρ(si ; di ) − ρ(si ; z) is
s
the maximum amount that may not be available to Eve, if
she has a min-cut ρ(si ; z). Again, we assume unit capacity
links and normalize the information in a message to ”1”
accordingly.

7

VI. A PPLICATIONS
In previous sections we suggested an SMSM code and
proved that under the suggested code an eavesdropper which
can capture a subset of the packet’s traversing the network
(up to w packets) is kept ignorant regarding each packets
content, under the Individual Security constraint, without
compromising the rate (i.e., achieving full network capacity).
In this section, we show several common applications which
exemplify the applicability of the suggested code to a diverse
range of protocols and applications. The first two examples
include only a single source, merely to show the applicability
of the individual secrecy setup. The third example is multisource in nature, and includes all aspects of our solution.
A. Data Centers
One of the most prominent facilities characterizing our
new information explosion era are distributed Data Centers.
Such facilities, which aim to cope with the rapidly increasing
volumes of data generated, archived and expected to be accessible, are vital to many services such as video sharing, social
networks, peer-to-peer cloud storage and many more. Google’s
GFS [36], Amazon’s Dynamo [37], Google’s BigTable [38],
Facebook’s Apache Hadoop [39], Microsoft’s WAS [40] and
LinkedIn’s Voldemort [41] are just a few examples of such
ubiquitous applications. Obviously, the security and reliability
of such Data Centers are critical for such applications to be
adopted by users and organizations.
In the basic non-secure model [42], [43], a source s needs
to store a file M which is decomposed into k messages, in v
servers (nodes), such that any legitimate user d (destination)
can reconstruct the file by collecting the stored information
from any l servers (l = ρ(s, di ) ≥ k). The secured version
constraints the stored chunks such that an eavesdropper which
can observe the information stored at any w servers will be
kept ignorant regarding the actual file stored (see Figure 4).
For the secured version, we can leverage the individualSMSM coding scheme suggested herein to enhance the nonsecure solution suggested in [24], [44]–[47], which consider
each node in the network as a server which maintains pieces
of data using RLNC. We will be able to guarantee that
any eavesdropper that can access any w servers will have
no information regarding any stored message individually
(zero mutual information regarding each message separately).
Specifically, each source s encodes the original data file M
using the individual security coding scheme suggested herein
(Sections IV and VII) and then uploads the encoded packets to
the v servers. The number and the size of packets uploaded to
the servers in the secure solution suggested are as in the nonsecure model; thus, we obtain the full capacity of the system.
It is important to note that utilizing the individual security
coding scheme suggested in this paper, one not only ensures
individual secrecy from potential eavesdroppers, but also can
guarantee privacy from the hosting servers themselves, such
that, each server not only will not be able to decode the
original data but will have zero information regarding any of
the stored message individually. For example, assume that in
the example depicted in Figure 4, the source s (private user)

Figure 4: Individual Secure Data Center, with 8 servers.
The source needs to store a file M with 4 messages, where
any legitimate user (destination) which is connected to 4
servers should be able to decode the 4 original messages.
In the individual secure coding scheme of this application,
we assume the existence of an eavesdropper, which is able
to obtain information from any 2 servers. We wish that this
eavesdropper will not gain any information on each specific
message.
wants to store a file M in the cloud. To do that, the source
can utilize 3 different cloud storage providers, such as Google
Drive, Microsoft OneDrive, Dropbox, etc. However, the source
wants to keep the original information private. Hence, by
encoding the original data using the individual security coding
scheme suggested at the source, and then uploading at most
~i , . . . , Y
~i to any provider, the provider
3 encoded packets Y
1
3
will store the packets in their servers v, but these will be kept
ignorant of the original file.
B. Wireless Networks
The inherent broadcast nature of the wireless medium makes
network coding techniques pertinent for wireless networks.
Specifically, relying on network coding, instead of sending
packets (unicast, multicast or broadcast packets) to each intended addressee individually, a source (or an intermediate
node which needs to relay packets toward the destination) can
transmit a manipulation (usually a linear combination) of the
packets destined to the various receivers. A receiver collecting
sufficient number of such combinations (coded packets) can
reconstruct (decode) the original packets. Relying on NC when
the channel is lossy, i.e., there is a probability that a sent packet
will not be received (decoded) by its intended receiver (receivers), has great advantages as instead of resending each uncoded packet until received correctly by its intended receiver,
a sender keeps sending combinations of the original packets
until each receiver collects a sufficient number of combinations
(e.g., [48]–[54]). Accordingly, a sender can a priori estimate
the number of coded packets needed according to the most

8

Figure 5: Individual Secure Wireless Network. The source
needs to disseminate 4 message over a wireless network to
3 legitimate users. In the individual secure model, we assume
the existence of an eavesdropper. However, due to interference,
collisions (low SINR) or low SNR, each of the receivers has a
different packet loss rate, according to the physical constraints
in the wireless networks.

lossy channel and send coded packets accordingly, without
relying on any feedbacks mechanism.
The secured version of this data dissemination problem
requires that an eavesdropper with a degraded channel which
can obtain only a subset of the transmitted packet will not
be able to attain any information regarding any of the original packets. Utilizing the individual security coding scheme
suggested in this paper, in which the source estimates the
number of packets needed to be sent according to the estimated
packet loss to each receiver, encodes the messages before the
wireless transmission according to the procedure presented in
Section IV and the anticipated packet loss to the eavesdropper
and broadcast the coded packets ensures that the legitimate
users will be available to obtain the original transmitted data
while any eavesdropper with higher packet loss rate will be
kept ignorant. A simple illustration is given in Figure 5: a
transmitter utilizing MU-MIMO techniques to direct the beams
toward its intended receivers such that eavesdroppers which
are sparsely scattered are expected to experience a lower
quality channel hence higher packet loss than the intended
receivers; the transmitter is utilizing the individual-SMSM
coding scheme suggested in Section IV, ensuring individual
security as proved in this paper.
C. Live Broadcast of Video with Multi-Path Streaming
Multi-Path routing techniques which enable the use of
multiple alternative paths between a source and a destination
through the network, has been widely exploited over the years
to provide a variety of benefits such as load balancing, fault
tolerance, bandwidth enhancement, etc. One such ubiquitous
example is LiveU innovative solution for distributing live video
streams via wireless networks [55], [56]. In these systems,
the real-time recorded video is encoded in packets by the

source. These encoded packets include pieces of the data to be
transmitted through different distributed media. For example,
the pieces of the data transmitted over various technologies
such as cellular networks, WiFi, satellite, fiber internet, etc. or
various providers, e.g., Sprint, T-Mobile, AT&T Verizon, etc.
A local server at the legitimate client decodes the data received
from the different distributed media. This distributed streaming
system maintains a high-quality viewer experience and costefficiency since the source can adapt the number of pieces
dynamically to be transmitted by the different media. For
example, if the connection using cellular or WiFi is lost during
the real-time transmission, the source can route the pieces of
the data dynamically by other connections or medias, taking
into account the cost of each transmission by the optional
connections.
In context to individual security suggested herein, we consider the case where there is an eavesdropper which has
access to only a subset of the connections during the realtime distributed streaming (we assume that the eavesdropper
can access any set of the streams unknown to the source, yet
only a subset thereof). Utilizing the individual security coding
scheme suggested in this paper, i.e., encoding the packets prior
to the transmission, according to the coding scheme suggested
in Section IV, guarantees Individual Secure Live Broadcast of
Video with Multi-Path Streaming, such that an eavesdropper
which can capture at most w streams transmitted over the
different distributed medias is kept ignorant in the sense
of having zero mutual information, regarding any set of ks
messages individually, yet may potentially obtain insignificant
information about mixtures of packets transmitted. Figure 6
depicts a graphical representation of this system.

Figure 6: Individual Secure Live Broadcast of Video with
Multi-Path Streaming. The sources s1 , s2 needs to transmit
the real-time recorded video Ms1 , Ms2 , respectively, encoded
~1 , . . . , Y
~5 from each source, over the
by LNC to 5 packets Y
different medias. The intermediate providers, such as cellular
networks, WiFi, satellite, fiber internet, etc may use LNC
before their routing transmission. Then, the legitimate clints
which received from a local provider cloud server all the packets, can decodes all the data. In the individual secure model
of this problem, we assume the existence of an eavesdropper,
which is able to obtain information from any 4 connections.
However, the individual secure code suggested herein, assure
that the eavesdropper is not able to decode the original
recorded information from the wiretapped connections.

9

VII. L INEAR C ODE C ONSTRUCTION FOR
I NDIVIDUAL -SMSM
The suggested code given in Section IV is based
on random coding. Therefore, in that case, the individual secrecy constraint holds only asymptotically, that is,
H(Ms,j |Zw )/H(Ms,j ) → 1 as k grows. In this section, we
design a structured linear code, which results in zero mutual
information, such that there is no requirement for k to grow,
yet, without any decrease in the rate or any message “blow-up”
by extra randomness. Hence, we prove the following corollary.
Corollary 2. With binary linear code, ks -individual security
in SMSM networks holds, keeping an eavesdropper which
observes ρ(s; z) links ignorant with respect to any set of
ks ≤ k − w messages, if form each source s ∈ S to
each destination d ∈ D, ρ(s, d) ≥ k, for all d ∈ D,
ρ(S, d) ≥ (k)|S|, ρ(s; z) ≤ w and k satisfies
'
&
ρ(s, d)
≥ 2.
k≥
ρ(s, d) − ρ(s; z)
We may now turn to the detailed construction and proof of
the Individual-SMSM structured linear code.
1) Codebook Generation: Let C be a binary linear code of
length k and dimension w, and set k 0 = k − w. Then, let

Proposition 1. At each source node, s, the encoding operation, for each column 1 ≤ i ≤ c of Ms,1 (i); . . . ; Ms,k (i) bits,
is given by
Xs (i)T

(2)

Proof. Define Xs (i)T according (2). We wish to show that
this definition is indeed consistent with (1), that is, using the
definition in (2) the bits Ms,1 (i); . . . ; Ms,k0 (i) define the coset
in which Xs (i) resides, and, furthermore, the remaining w bits,
Ms,k0 +1 (i); . . . ; Ms,k (i), uniquely define the word within the
coset.
To this end, take the transposed of equation (2), and multiply
it by H. We have:
HXs (i)

~ ?1 )T + . . . + HMs,k0 (i)(G
~ ?k0 )T
HMs,1 (i)(G
~ 1 )T + . . . + HMs,k (i)(G
~ w )T
+HMs,k0 +1 (i)(G


 
0
1
 0 
 0 


 
= Ms,1 (i)  .  + . . . + Ms,k0 (i)  . 
 .. 
 .. 

=

0

~ 1; H
~ 2; . . . ; H
~ k0 ] ∈ {0, 1}k0 ×k
H = [H

1

+Ms,k0 +1 (i)0 + . . . + Ms,k (i)0

Ms,1 (i)


..
,

.
Ms,k0 (i)


be a parity check matrix, which we assume has rank k 0 . This
linear code defines 2k−w cosets, one of them is the code itself.
We denote the cosets by {Am } , 1 ≤ m ≤ 2k−w . Note
that each coset is of size 2w . Hence the cosets of this code
correspond to the bins we used in Section IV.
Let G be a generator matrix for C. We thus denote
~ 1; G
~ 2; . . . ; G
~ w ] ∈ {0, 1}w×k ,
G = [G
and we select a matrix
0

~ ?1 ; G
~ ?2 ; . . . ; G
~ ?k0 ] ∈ {0, 1}k ×k
G? = [G
with k 0 linearly independent rows from {0, 1}k \ C. That is,
G? spans the null space of C.
2) Source and legitimate Node encodings: At each source
node, s, the encoder selects, for each column i a codeword xk (e(i)) out of the 2w members of the coset Am ,
where m is given by the index Ms,1 (i); . . . ; Ms,k0 (i) and
e(i) = Ms,k0+1 (i); . . . ; Ms,k (i). That is similar to Section IV,
k 0 = k − w bits of the column choose the coset, and the
remaining w bits choose the codeword within the coset. This
is equivalent to letting Xs (i) be a choice from the 2w solutions
of
(Ms,1 (i); . . . ; Ms,k0 (i)) = HXs (i).

~ ?1 + . . . + Ms,k0 (i)G
~ ?k0
= Ms,1 (i)G
~ + . . . + Ms,k (i)G
~w
+Ms,k0 +1 (i)G
 ? 1
G
.
= Ms (i)T
G

(1)

Again note that Xs is of the same size as Ms .
Proposition 1 below shows that, in fact, Xs can be easily
computed using matrix multiplication.

=

~ ? is our choice of a
where the second inequality is since G
~?
basis to the null space of the code, hence, we can take G
? T
~
such that H(G ) = I; Moreover, since H is a parity check
matrix for the code, it is orthogonal to all codewords. Thus,
the first k 0 bits define the coset.
Now, since the bits Ms,k0 +1 (i); . . . ; Ms,k (i) create a linear
combination of codewords, the addition of such a linear
combination dose note change the coset. Xs (i)T remains in
~ 1; . . . ; G
~ w)
the same coset regardless of these bits. Yet, as (G
w
is of rank w, all 2 possibilities for the linear combination are
distinct, creating distinct vectors Xs (i)T within the coset.
Then, the network code is similar to Section IV. That is, the
sources transmit linear combinations of the rows, with random
coefficients. Nodes transmit random linear combinations of the
vectors in Sv , which is maintained by each node according to
the messages received at the node.
A. Reliability
As for the reconstruction of Xs , the reliability part using
RLNC is almost a direct consequence of [2]. Again, the mincut is given by Theorem 1, and, the legitimate nodes can easily
reconstruct Xs for each s.
Now, since the code C is chosen to be (k, w) code, each partial column Ms,1 (i); . . . ; Ms,k0 (i) can be seen as a syndrome
of C with respect to a k 0 × k parity-check matrix H (as given

10

in [57, Section 4]). Thus, each destination can map Xs back
to Ms . First, compute the bin index: where
(Ms,1 (i); . . . ; Ms,k0 (i)) = HXs (i).
Then, Ms,k0 +1 (i); . . . ; Ms,k (i) are simply the index of Xs
within that bin.
In the same way, using a gossip protocol, the reliability
proof is almost a direct consequence of [29, Theorem 1].
Hence, the number of rounds required is given by Theorem 3.
B. Information Leakage at the Eavesdropper
Denoted by C the code and by Xs the set of codewords cor~ s,1 . . . M
~ s,k . We assume that the eavesdropper
responding to M
has full knowledge of the code C as well.
As given in Section IV-B, to analyze the information leakage
at the eavesdropper, note that Eve has access to at most w
linear combinations on the rows of Xs . We will assume these
linear combinations are in fact independent, and since Eve
has access to the coefficients, we will assume Eve can even
use Gaussian elimination and have access to w rows from the
original matrix Xs .
Next, we note that the columns of Xs are independent
(by the construction of the codebook, as creation Xs is done
independently per-column). Hence, it suffices to consider the
information leakage for each column i ∈ {1, . . . , c} from
Xs separately. Thus, using techniques given in [57], we
|Zw ) by first
calculate the eavesdroppers uncertainty H(Mk−w
s
(i)|Z
(i))
for
each
equally
likely
column.
evaluating H(Mk−w
w
s
If a coset of C contains at least one word that agrees with
Zw (i), we say that the coset is consistent with Zw (i). Let
N (C, Zw (i)) denote the total number of cosets consistent with
Zw (i). If the number of words consistent with Zw (i) in each
coset is the same, we will have
H(Ms,j (i)|Zw (i)) = log2 N (C, Zw (i)).
For an (k, w) code C, the maximum possible value
0
for N (C, Zw (i)) is the total number of cosets, 2k . If
0
N (C, Zw (i)) = 2k , we say that Zw (i) is individually secured
by C, since the total number of words which can be consistent
0
with Zw (i) is 2k (as Zw (i) is of length w = k − k 0 ), hence
they are all in different cosets, hence H(Ms,j (i)|Zw (i)) =
0
log2 N (C, Zw (i)) and P r(Ms (i)|Zw (i)) = 1/2k for every
possible column Ms (i). The following lemma states a condition for a column Zw (i) at the eavesdropper to be individually
secured by a code C.
Lemma 1. Let (k, w) binary linear code C have a generator
matrix G, where Gj denote the j-th column of G. Consider an
eavesdroppers observation Zw (i), with access to w positions
{j : XTs,j (i) 6=?} = {j1 , j2 , . . . , jw } from a certain column
i ∈ {1, . . . , c} of the original matrix Xs . Zw (i) is individually
secured by C iff the matrix Gw = [Gj1 ; Gj2 . . . ; Gjw ] has rank
w for any set of indices {j1 , j2 , . . . , jw }.
Proof. Remember
that the encoding is defined by
 ? 
G
T
Ms (i)
. The eavesdropper has access to at
G
most w bits from each codeword. Eve is interested in

Figure 7: Binning and source encoding process for StrongSMSM.
the linear combination which created the codeword Xs (i)T ,
Ms (i)T . If Gw has rank w, the code C has codewords
with all possible sequences of 2w in the w positions
T
{j : Xs,j
(i) 6=?} = {j1 , j2 , . . . , jw } obtained by the
eavesdropper. Since Eve sees only w positions, there are
k − w additional dimensions, thus there are 2k−w possibilities.
Again, since cosets are obtained by translating the code C,
each coset of C has one of these possibilities.
If, however, Gw has rank less than w, the code C does not
have all 2w possible sequences in the w revealed positions.
Hence, there exists at least one coset that does not contain a
given sequence which matches Eve’s data in the w revealed
0
positions, and therefore N (C, Zw (i)) < 2k .
To conclude, if one uses a good linear (k, w) code to create
the cosets, for Eve, all matching codewords are equiprobable
; Zw ) = 0.
and reside in different cosets, hence, I(Mk−w
s
VIII. C ODE C ONSTRUCTION AND A P ROOF
FOR S TRONG -SMSM
In this section, we design a random code, which results
with strong-secrecy, i.e., requiring Eve’s mutual information
with all messages simultaneously to be zero, yet, at price of
rate as given in [5]. However, using the suggest random code
herein, the field size is determined only by the network coding
scheme, that is, only by the requirement for reliability, and is
not increased by the strong-security constraints.
At each source node s ∈ {1, . . . , |S|}, we randomly map
each column of the message matrix Ms . As depicted in Figure 7, in the code construction phase, for each possible column
of the s-th message matrix we generate a bin, containing
several columns. The number of such columns corresponds to
w, the number of packets that the eavesdropper can wiretap,
in a relation that will be made formal in the sequel. Then, to
encode, for each column of the message matrix, we randomly
select a column from its corresponding bin. This way, a new,
n × c message matrix Xs is created. Specifically, a StrongSMSM code at the s-th source node consists of a messages
~ s,1 . . . M
~ s,k messages of length c bits over the
matrix Ms of M

11

binary field, we denote the set of matrices by Ms ; A discrete
memoryless source of randomness over the alphabet R and
some known statistics pR ; An encoder,
f : Ms × R → Xs ∈ {0, 1}n×c
which maps each message matrix Ms to a matrix Xs of
codewords. This message matrix contains n ≥ k + w new
messages of size c.
The need for a stochastic encoder is similar to most encoders ensuring information theoretic security, as randomness
is required to confuse the eavesdropper about the actual
information [58]. Hence, we define by Rk the random variable
encompassing the randomness required for the k messages at
the source node, and by ∆ the number of columns in each bin.
We may now turn to the detailed construction and analysis.
1) Codebook Generation: Set ∆ = 2w+n . Where
Qn P (x) ∼
Bernoulli(1/2), using a distribution P (X n ) = j=1 P (xj ),
for each possible column in the message matrix generate ∆
independent and identically distributed codewords xn (e), 1 ≤
e ≤ ∆. where  ≥ 1/n.
2) Source and legitimate Node encodings: For each column
i of the s-th message matrix Ms , the s-th source node selects
uniformly at random one codeword xn (e) from the i-th bin.
Therefore, the s-th source Strong-SMSM matrix Xs contains c
randomly selected codewords of length n, one for each column
of the s-th message matrix. Then, the sources transmit linear
combinations of the rows, with random coefficients. Nodes
transmit random linear combinations of the vectors in Sv ,
which is maintained by each node according to the messages
received at the node.
The reliability in the Strong-SMSM algorithm is inherited
from the reliability in RLNC. That is if min-cuts are ρ(s, d) ≥
k + w and ρ(S, d) ≥ (k + w)|S| for each s ∈ S and d ∈ D
then k + w = n messages can be transmitted reliably from
each source to all destinations. Since the transformation Ms
to Xs can be inverted, the destinations cad decode the original
messages.
A. Information Leakage at the Eavesdropper
We now prove the strong-security constraint is met. In
particular, for the strong constraint, we wish to show that
I(Ms ; Zw ) is small for all s ∈ S. We will do that by showing
that given Zw , Eve’s information, all possibilities for Ms are
equally likely, hence Eve has no intelligent estimation for Ms .
Denote by Cn the random codebook and by Xs the set
~ s,1 . . . M
~ s,k . To analyze the
of codewords corresponding to M
information leakage at the eavesdropper, note that Eve has
access to at most w linear combinations on the rows of Xs . We
will assume these linear combinations are in fact independent,
and since Eve has access to the coefficients, we will assume
Eve can even use Gaussian elimination and have access to w
rows from original matrix Xs .
Next, note that the columns of Xs are independent (by the
construction of the codebook, creating Xs is done independently per-column; c columns are used only to reduce the
NC overhead). Hence, it suffices to consider the information
leakage for each column i ∈ {1, . . . , c} from Xs separately.

For each column i of Ms , the encoder has ∆ independent and
identically distributed codewords, out of which one is selected.
Hence, there is an exponential number of codewords, from the
eavesdropper’s perspective, that can generate a column in Xs ,
and we require that Eve is still confused even given the w bit
from each column.
Let Zw (i) be the w bits Eve has from column i. Denote
l = n − w. Define by Sh(Zw (i), l) the set of all n-tuples
consistent with Zw (i), i.e.,
Sh(Zw (i), l) = {bn : bn (SZ ) = Zw (i)},
where SZ denotes indices of the rows Eve has. Clearly, there
are 2l tuples in Sh(Zw (i), l).
We assume Eve has the codebook, yet does not know which
column from each bin is selected to be the codeword. Hence,
we wish to show that given Zw (i), Eve will have at least one
candidate per bin. The probability for a codeword to fall in a
given shell is
P r(Xns (i) ∈ Cn ∩ Xns (i) ∈ Sh(Zw (i), l))
2(n−w)
Vol(Sh(Zw (i), l))
=
.
2n
2n
In each bin of Cn , we have ∆ = 2w+n codewords. Thus, the
average number of codewords Eve sees in her shell, per bin
is
2w+n ∗ 2n−w
|{m(i) : X n (i) ∈ Sh(Z(i), l)}| =
= 2n .
2n
Hence, we can conclude that on average, and if n is not too
small, for every column in Ms Eve has a few possibilities
in each bin, hence cannot locate the right bin. However, it
is still important to show that all bins have (asymptotically)
equally likely number of candidate codewords, hence Eve
cannot locate a preferred bin.
To this end, we proved that the average number of codewords per column is very close to 2n with high probability.
We wish to show that the probability that the actual number
of options deviates from the average by more than ε is small.
Define
=

EC1 (Z(i), l) := P r{(1 − ε)2n ≤
|m(i) : Xsn (i) ∈ Sh(Zw (i), l)| ≤ (1 + ε)2n }.
By the Chernoff bound, we have
0 n

P r(EC1 (Z(i), l)) ≥ 1 − 2−ε 2 .
Due to the super exponential decay in n, when taking a union
bound over all columns, the probability that Eve decodes
correctly some column is small. Hence, by the chain rule for
entropies, since allP
the codewords in the codebook are indec
pendent H(Xs ) = i=1 H(Xs (i)), for Eve, all codewords are
almost equiprobable and I(Ms ; Zw ) → 0.
IX. C ONCLUSIONS
In this paper, we proposed SMSM codes under an Individual
Security constraint. In this model, the eavesdropper is kept
ignorant, in the sense of having zero mutual information
regarding each message separately, yet may potentially obtain

12

insignificant information about mixtures of packets transmitted. In fact, it ensures Eve is kept ignorant of any set of k − w
messages. That is, guarantee zero mutual information, with
respect to any set of k − w messages.
We completely characterized the rate region for individually
secure MSM. Specifically, we showed that secure communication is achievable up to the min-cut, that is, without any
decrease in the rate or any message “blow-up” by extra randomness. Moreover, we provided a code for Strong-SMSM by
extra randomness, i.e., requiring Eve’s mutual information with
all messages simultaneously to be zero. While this included
a rate loss, it is important to note that in the code suggested
the alphabet size did not increase with the network parameters
due to the strong-security constraint.
Finally, we showed a few examples out of many important
applications, like data centers, wireless networks, gossip and
live broadcasting of video, for which the individual security
coding schemes suggested is applicable, and achieves the full
capacity of these systems.
R EFERENCES
[1] S.-Y. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE
transactions on information theory, vol. 49, no. 2, pp. 371–381, 2003.
[2] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and
B. Leong, “A random linear network coding approach to multicast,”
IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413–
4430, 2006.
[3] N. Cai and R. W. Yeung, “Secure network coding,” in Information
Theory, 2002. Proceedings. 2002 IEEE International Symposium on.
IEEE, 2002, p. 323.
[4] T. Chan and A. Grant, “Capacity bounds for secure network coding,”
in Communications Theory Workshop, 2008. AusCTW 2008. Australian.
IEEE, 2008, pp. 95–100.
[5] N. Cai and R. W. Yeung, “Secure network coding on a wiretap network,”
Information Theory, IEEE Transactions on, vol. 57, no. 1, pp. 424–435,
2011.
[6] S. Y. El Rouayheb and E. Soljanin, “On wiretap networks II,” in
Information Theory, 2007. ISIT 2007. IEEE International Symposium
on. IEEE, 2007, pp. 551–555.
[7] D. Silva and F. R. Kschischang, “Security for wiretap networks via
rank-metric codes,” in Information Theory, 2008. ISIT 2008. IEEE
International Symposium on. IEEE, 2008, pp. 176–180.
[8] S. El Rouayheb, E. Soljanin, and A. Sprintson, “Secure network coding
for wiretap networks of type II,” Information Theory, IEEE Transactions
on, vol. 58, no. 3, pp. 1361–1371, 2012.
[9] N. Cai and R. W. Yeung, “A security condition for multi-source
linear network coding,” in Information Theory, 2007. ISIT 2007. IEEE
International Symposium on. IEEE, 2007, pp. 561–565.
[10] Z. Zhang and R. W. Yeung, “A general security condition for multisource linear network coding,” in Information Theory, 2009. ISIT 2009.
IEEE International Symposium on. IEEE, 2009, pp. 1155–1158.
[11] N. Cai, “Valuable messages and random outputs of channels in linear
network coding,” in Information Theory, 2009. ISIT 2009. IEEE International Symposium on. IEEE, 2009, pp. 413–417.
[12] N. Cai and T. Chan, “Theory of secure network coding,” Proceedings
of the IEEE, vol. 99, no. 3, pp. 421–437, 2011.
[13] T. H. Chan and A. Grant, “Network coding capacity regions via entropy
functions,” IEEE Transactions on Information Theory, vol. 60, no. 9,
pp. 5347–5374, 2014.
[14] D. Kobayashi, H. Yamamoto, and T. Ogawa, “Secure multiplex coding
attaining channel capacity in wiretap channels,” IEEE Transactions on
Information Theory, vol. 59, no. 12, pp. 8131–8143, 2013.
[15] A. S. Mansour, R. F. Schaefer, and H. Boche, “Secrecy measures for
broadcast channels with receiver side information: Joint vs individual,”
in Information Theory Workshop (ITW), 2014 IEEE. IEEE, 2014, pp.
426–430.
[16] Y. Chen, O. O. Koyluoglu, and A. Sezgin, “On the individual secrecy
rate region for the broadcast channel with an external eavesdropper,”
in 2015 IEEE International Symposium on Information Theory (ISIT).
IEEE, 2015, pp. 1347–1351.

[17] A. S. Mansour, R. F. Schaefer, and H. Boche, “The individual secrecy
capacity of degraded multi-receiver wiretap broadcast channels,” in 2015
IEEE International Conference on Communications (ICC). IEEE, 2015,
pp. 4181–4186.
[18] ——, “On the individual secrecy capacity regions of the general,
degraded and gaussian multi-receiver wiretap broadcast channel,” IEEE
Transactions on Information and Security, 2016, vol. 11, no. 9, pp. 2107–
2122, 2016.
[19] M. Goldenbaum, R. F. Schaefer, and H. V. Poor, “The multiple-access
channel with an external eavesdropper: Trusted vs. untrusted users,” in
2015 49th Asilomar Conference on Signals, Systems and Computers.
IEEE, 2015, pp. 564–568.
[20] Y. Chen, O. O. Koyluoglu, and A. H. Vinck, “On secure communication over the multiple access channel,” International Symposium on
Information Theory and Its Applications (ISITA), 2016 IEEE, 2016.
[21] K. Bhattad and K. R. Narayanan, “Weakly secure network coding,”
NetCod, Apr, vol. 104, 2005.
[22] L. Lima, M. Médard, and J. Barros, “Random linear network coding:
A free cipher?” in Information Theory, 2007. ISIT 2007. IEEE International Symposium on. IEEE, 2007, pp. 546–550.
[23] J. Claridge and I. Chatzigeorgiou, “Probability of partially solving random linear systems in network coding,” arXiv preprint
arXiv:1607.04725, 2016.
[24] S. Deb, M. Médard, and C. Choute, “Algebraic gossip: A network coding
approach to optimal multiple rumor mongering,” Information Theory,
IEEE Transactions on, vol. 52, no. 6, pp. 2486–2507, 2006.
[25] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker,
H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for
replicated database maintenance,” in Proceedings of the sixth annual
ACM Symposium on Principles of distributed computing. ACM, 1987,
pp. 1–12.
[26] S. Deb, M. Medard, and C. Choute, “On random network coding based
information dissemination,” in Information Theory, 2005. ISIT 2005.
Proceedings. International Symposium on. IEEE, 2005, pp. 278–282.
[27] B. Haeupler, “Analyzing network coding gossip made easy,” in Proceedings of the 43rd annual ACM symposium on Theory of computing.
ACM, 2011, pp. 293–302.
[28] A. S. Mansour, R. F. Schaefer, and H. Boche, “The individual secrecy
capacity of the gaussian SISO and degraded gaussian MIMO multireceiver wiretap channel,” in 2015 IEEE 16th International Workshop
on Signal Processing Advances in Wireless Communications (SPAWC).
IEEE, 2015, pp. 365–369.
[29] A. Cohen, B. Haeupler, C. Avin, and M. Médard, “Network coding
based information spreading in dynamic networks with correlated data,”
IEEE Journal on Selected Areas in Communications, vol. 33, no. 2, pp.
213–224, 2015.
[30] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and
L. M. Tolhuizen, “Polynomial time algorithms for multicast network
code construction,” IEEE Transactions on Information Theory, vol. 51,
no. 6, pp. 1973–1982, 2005.
[31] R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, “Randomized
rumor spreading,” in Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. IEEE, 2000, pp. 565–574.
[32] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of
aggregate information,” in Foundations of Computer Science, 2003.
Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003, pp. 482–
491.
[33] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip
algorithms,” Information Theory, IEEE Transactions on, vol. 52, no. 6,
pp. 2508–2530, 2006.
[34] J. Feldman, T. Malkin, R. A. Servedio, and C. Stein, “Secure network
coding via filtered secret sharing.” Citeseer.
[35] B. K. Dey, S. Jaggi, and M. Langberg, “Sufficiently myopic adversaries
are blind,” in Information Theory (ISIT), 2015 IEEE International
Symposium on. IEEE, 2015, pp. 1164–1168.
[36] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file system,”
in ACM SIGOPS operating systems review, vol. 37, no. 5. ACM, 2003,
pp. 29–43.
[37] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman,
A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo:
amazon’s highly available key-value store,” ACM SIGOPS operating
systems review, vol. 41, no. 6, pp. 205–220, 2007.
[38] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, “Bigtable: A distributed
storage system for structured data,” ACM Transactions on Computer
Systems (TOCS), vol. 26, no. 2, p. 4, 2008.

13

[39] D. Borthakur, J. Gray, J. S. Sarma, K. Muthukkaruppan, N. Spiegelberg,
H. Kuang, K. Ranganathan, D. Molkov, A. Menon, S. Rash et al.,
“Apache hadoop goes realtime at facebook,” in Proceedings of the
2011 ACM SIGMOD International Conference on Management of data.
ACM, 2011, pp. 1071–1080.
[40] B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie,
Y. Xu, S. Srivastav, J. Wu, H. Simitci et al., “Windows azure storage:
a highly available cloud storage service with strong consistency,” in
Proceedings of the Twenty-Third ACM Symposium on Operating Systems
Principles. ACM, 2011, pp. 143–157.
[41] A. Auradkar, C. Botev, S. Das, D. De Maagd, A. Feinberg, P. Ganti,
L. Gao, B. Ghosh, K. Gopalakrishna, B. Harris et al., “Data infrastructure at linkedin,” in Data Engineering (ICDE), 2012 IEEE 28th
International Conference on. IEEE, 2012, pp. 1370–1381.
[42] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE
Transactions on Information Theory, vol. 56, no. 9, pp. 4539–4551,
2010.
[43] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A survey on
network codes for distributed storage,” Proceedings of the IEEE, vol. 99,
no. 3, pp. 476–489, 2011.
[44] S. Acedanski, S. Deb, M. Médard, and R. Koetter, “How good is random
linear coding based distributed networked storage,” in Workshop on
Network Coding, Theory and Applications, 2005, pp. 1–6.
[45] B. Haeupler and M. Médard, “One packet suffices-highly efficient
packetized network coding with finite memory,” in Information Theory
Proceedings (ISIT), 2011 IEEE International Symposium on. IEEE,
2011, pp. 1151–1155.
[46] B. Haeupler, M. Kim, and M. Médard, “Optimality of network coding
with buffers,” in Information Theory Workshop (ITW), 2011 IEEE.
IEEE, 2011, pp. 533–537.
[47] F. H. Fitzek, T. Toth, A. Szabados, M. V. Pedersen, D. E. Lucani,
M. Sipos, H. Charaf, and M. Medard, “Implementation and performance
evaluation of distributed cloud storage solutions using random linear
network coding,” in Communications Workshops (ICC), 2014 IEEE
International Conference on. IEEE, 2014, pp. 249–254.
[48] D. S. Lun, M. Médard, and R. Koetter, Efficient operation of wireless
packet networks using network coding. IWCT, 2005, vol. 5.
[49] M. Kim, M. Médard, and J. Barros, “Algebraic watchdog: mitigating
misbehavior in wireless network coding,” IEEE Journal on Selected
Areas in Communications, vol. 29, no. 10, pp. 1916–1925, 2011.
[50] R. A. Popa, A. Chiesa, T. Badirkhanli, and M. Médard, “Going beyond
pollution attacks: Forcing byzantine clients to code correctly,” arXiv
preprint arXiv:1108.2080, 2011.
[51] V. N. Talooki, R. Bassoli, D. E. Lucani, J. Rodriguez, F. H. Fitzek,
H. Marques, and R. Tafazolli, “Security concerns and countermeasures
in network coding based communication systems: A survey,” Computer
Networks, vol. 83, pp. 422–445, 2015.
[52] U. Speidel, E. Cocker, P. Vingelmann, J. Heide, and M. Médard, “Can
network coding bridge the digital divide in the pacific?” in Network
Coding (NetCod), 2015 International Symposium on. IEEE, 2015, pp.
86–90.
[53] D. S. Lun, M. Médard, R. Koetter, and M. Effros, “On coding for reliable
communication over packet networks,” Physical Communication, vol. 1,
no. 1, pp. 3–20, 2008.
[54] J. Hansen, D. E. Lucani, J. Krigslund, M. Médard, and F. H. Fitzek,
“Network coded software defined networking: enabling 5g transmission
and storage networks,” IEEE Communications Magazine, vol. 53, no. 9,
pp. 100–107, 2015.
[55] LiveU. (2017) Live cellular uplinking for television and the web.
[Online]. Available: Cellular-uplinking-white-paper-LiveU.doc
[56] ——. (2017) The Internet can be a scary place for your live video:
don’t let a bad stream cost you your audiences. [Online]. Available:
http://www.pts.gr/files/LiveU-Live-Streaming-Whitepaper.pdf
[57] L. H. Ozarow and A. D. Wyner, “Wire-tap channel ii,” in Advances in
Cryptology. Springer, 1985, pp. 33–50.
[58] M. Bloch and J. Barros, Physical-Layer Security: From Information
Theory to Security Engineering. Cambridge University Press, 2011.

