A KeyBased Error Control Scheme forNetwork Coding
Danilo Silva and Frank R. Kschischang
Department of Electrical and Computer Engineering, University of TorontoToronto, Ontario M5S 3G4, Canada,
{
danilo, frank
}
@comm.utoronto.ca
Abstract
—This work presents an error control scheme fornetwork coding under an adversarial error model. The schemerelies on the assumption that the transmitter and receiver sharea key that is secret from the adversary. The scheme can achievea rate that is signiﬁcantly higher than what can be achievedwithout a shared key. Moreover, differently from previous keybased approaches, the proposed scheme does not require the ﬁeldsize to be arbitrarily large. The scheme is practical, conceptuallysimple, and compatible with both coherent and random networkcoding.
I. I
NTRODUCTION
The problem of error control in linear network coding hasattracted signiﬁcant interest recently, and many quite differentapproaches have been proposed. The common model is thatof a matrix channel over a ﬁnite ﬁeld, where rows of a matrixrepresent packets. Errors may occur due to imperfections onthe physical layer, or due to an adversary that arbitrarilyinjects corrupt packets, and propagate through the network,potentially contaminating legitimate packets.When the network coding system is
coherent
, transmitterand receiver(s) (and any potential adversary) have completeknowledge of the network code. In contrast, this knowledge isunavailable or not required in a noncoherent system, the mostprominent example being when the network code is randomlyformed. Previous works on error correction include [1]–[3]for coherent network coding and [4]–[6] for random network coding. All of these works achieve approximately the samerate performance; namely,
2
t
redundant packets must be usedif
t
corrupt packets are injected.Higher rates can be achieved if certain assumptions aremade about the channel or the adversary. More precisely, theredundancy can be cut by half (
t
redundant packets for
t
corrupt packets) if either of the following assumptions aremade: the transmitter and receiver share a secret key [7];or the adversary chooses packets uniformly at random ratherthan in a worstcase fashion [8]. Moreover, it is possible forthe transmitter and receiver to share a secret key directlythrough the network coding channel if the adversary is causal[7], computationally bounded [7], or limited in eavesdroppingcapabilities [4], [9].A drawback of all previous keybased approaches is thatthey rely on both the ﬁeld size
and
the packet length beingarbitrarily large. This is strictly necessary to ensure that sucha scheme has a low probability of failure. However, a large
This work was supported by CAPES Foundation, Brazil.
ﬁeld size is not a reasonable assumption in practice and maypreclude a realworld implementation.In this paper, we present a keybased scheme that is bothpractical and conceptually simple. The scheme works for bothcoherent and random network coding. We give an explicitupper bound on the probability of failure, which can be madearbitrarily small by increasing either the ﬁeld size
or
the packetlength. In particular, realworld values for these parameters aresufﬁcient to ensure a low probability of failure.A main idea behind our approach is to show that thepresence of a key essentially
forces
the adversary to injectrandom packets, therefore allowing us to use the approach of [8] to obtain a higher rate.The remainder of the paper is organized as follows. Section II introduces the channel models and review previous(not keybased) error control schemes on which our schemerelies. Sections III and IV present our scheme in its versionsfor coherent and random network coding, respectively. Afurther discussion of our scheme is provided in Section V, andSection VI presents our conclusions. Some proofs are omitteddue to lack of space.II. P
RELIMINARIES
A. Notation
Let
F
n
×
mq
denote the set of all
n
×
m
matrices over the ﬁniteﬁeld
F
q
and let
T
n
×
m
denote the set of all
fullrank
n
×
m
matrices over the same ﬁeld. The
n
×
m
allzero matrix andthe
n
×
n
identity matrix are denoted by
0
n
×
m
and
I
n
×
n
,respectively, where the subscripts may be omitted when thereis no risk of confusion. The reduced row echelon (RRE) formof a matrix
M
will be denoted by
RRE
(
M
)
. The
minimumrank distance
of a code
C ⊆
F
n
×
mq
(see [6] and referencestherein) is denoted by
d
R
(
C
)
.
B. Channel Models
Let
X
∈
F
n
×
mq
be a matrix consisting of the packetstransmitted by the transmitter, let
Y
∈
F
N
×
mq
be a matrixconsisting of the packets received by the receiver, and let
Z
∈
F
t
×
mq
be a matrix consisting of the packets injected by theadversary. In a linear network coding channel, these matricesare related by
Y
=
AX
+
DZ
(1)where
A
∈
F
N
×
nq
and
D
∈
F
N
×
tq
are the transfer matricesfrom the transmitter to the receiver and from the adversary to
9781424434015/09/$25.00 ©2009 IEEE5
the receiver, respectively. We assume that the adversary knows
X
and can arbitrarily choose
Z
. A main assumption of thispaper is that the transmitter and receiver share a key that issecret from the adversary.We consider two speciﬁc submodels: coherent network coding and noncoherent (more speciﬁcally, random) network coding.For
coherent network coding
, we assume that:
•
The matrix
A
is a constant that is known to all;
•
The matrix
D
is arbitrarily chosen by the adversary.For
random network coding
, we instead assume that:
1
•
N
=
n
;
•
A
is a random matrix uniformly distributed on
T
n
×
n
;
•
D
is a random matrix with some distribution on
T
n
×
t
;
•
The matrices
A
,
D
and
X
are statistically independent.In this case, by taking
B
=
A
−
1
D
, it is possible to rewrite(1) as
Y
=
A
(
X
+
BZ
)
(2)where
•
B
is a random matrix uniformly distributed on
T
n
×
t
;
•
The pair
(
A,B
)
is independent from
X
.For random network coding, we will use this last formulationrather that (1), since it simpliﬁes the analysis considerably.
C. Coherent Network Coding Without a Shared Key
In this subsection we brieﬂy review the approach of [6] forerror control in coherent network coding. Here, no assumptionis made about a shared key.Let
C ⊆
F
n
×
mq
be a code with minimum rank distance
d
R
(
C
) =
d
. The transmission matrix is taken as a codeword
X
∈ C
. Let
ρ
=
n
−
rank
A
. It is shown in [6] that, provided
d >
2
t
+
ρ
, the receiver is always able to recover
X
.Decoding proceeds as follows. Let
Y
0
=
A Y
, where
Y
is given in (1). Then there exists a
(
n
+
δ
)
×
N
matrix
T
suchthat
rank
TY
0
=
rank
Y
and
TY
0
=
I
+ˆ
LI
T
U
r
0ˆ
V
(3)where
r
∈
F
n
×
mq
,
ˆ
L
∈ T
n
×
ρ
,
ˆ
V
∈ T
δ
×
m
and
U
is a subsetof
{
1
,...,n
}
with cardinality
ρ
. By taking
(
r,
ˆ
L,
ˆ
V
)
as input,the decoder of [6] is guaranteed to successfully recover
X
.More generally, let
e
r
−
X
denote the error word, and let
µ
=
rank
ˆ
L
, which (in the case of coherent network coding) isequal to
ρ
. Successful decodingis guaranteed provided
2
ǫ
+
µ
+
δ < d
, where
ǫ
is the minimum value of
rank
(
e
−
ˆ
LV
1
−
L
2
ˆ
V
)
for all
V
1
∈
F
µ
×
mq
and
L
2
∈
F
n
×
δq
. (Under the assumptions of coherent network coding, it is possible to show that
ǫ
≤
t
−
δ
,so the decoding condition becomes
2
t
+
ρ < d
+
δ
, i.e., thecorrection capability of
C
is increased whenever
δ >
0
.)
1
The assumption that
A
is uniform and independent from
D
is justiﬁedas follows. Let
M
∈ T
n
×
n
denote the actual network transfer matrix. If
M
is not uniform and independent from
D
, then the transmitter may
randomize
the its message by transmitting
RX
, where
R
∈ T
n
×
n
is a uniform randommatrix independent from any other variables. It follows that
Y
=
AX
+
DZ
,where
A
=
MR
∈ T
n
×
n
is uniform and independent from
D
.
The decoder of [6] admits an efﬁcient implementationwhen
C
is a maximumrankdistance (MRD) code. The logcardinality of an MRD code, for
m
≥
n
, is given by
log
q
C
=
m
(
n
−
d
+ 1)
. Thus, an efﬁcient coding schemeexists that can achieve a transmission rate of
n
−
2
t
−
ρ
packetswith zero probability of error.
D. Random Network Coding Without a Shared Key: TheSpecial Case of Random Errors
Several previous works exist for the problem of randomnetwork coding without a shared key. Below we review theapproach of [8], which is applicable for the special case wherethe adversary chooses the matrix
Z
uniformly at random from
T
t
×
m
.Let
v
≥
t
and let
U
∈
F
(
n
−
v
)
×
(
m
−
n
)
q
be a data matrix.Form the transmission matrix as
X
=
0
v
×
v
0
v
×
(
n
−
v
)
0
v
×
(
m
−
n
)
0
(
n
−
v
)
×
v
I
(
n
−
v
)
×
(
n
−
v
)
U
.
Let
B
=
B
1
B
2
and
Z
=
Z
1
Z
2
Z
3
, where
B
1
∈
F
v
×
tq
,
B
2
∈
F
(
n
−
v
)
×
tq
,
Z
1
∈
F
t
×
vq
,
Z
2
∈
F
t
×
(
n
−
v
)
q
and
Z
3
∈
F
t
×
(
m
−
n
)
q
. According to the model of Section IIB, thereceiver receives
Y
=
A
¯
Y
, where
¯
Y
=
X
+
BZ
=
B
1
Z
1
B
1
Z
2
B
1
Z
3
B
2
Z
1
I
+
B
2
Z
2
U
+
B
2
Z
3
.
It is shown in [8] that if
rank
B
1
Z
1
=
t
, then
RRE
(
Y
) =
RRE
¯
Y
=
˜
Z
1
0˜
Z
3
0
I U
0 0 0
for some
˜
Z
1
∈
F
t
×
vq
in RRE form and some
˜
Z
3
∈
F
t
×
(
m
−
n
)
q
.Thus, the receiver can easily extract
U
by simply converting
Y
to RRE form.The probability of decoding failure is upper bounded by
P
f
< P
f
1
+
P
f
2
, where
P
f
1
=
P
[
rank
B
1
< t
]
and
P
f
2
=
P
[
rank
Z
1
< t
]
. It is shown that [8]
P
f
1
=
P
f
2
<tq
1+
v
−
t
.
(4)It follows that a data rate of
m
−
tm
(
n
−
t
)
packets can be(asymptotically) achieved with an arbitrarily low probabilityof error. Such a rate has indeed been proved to be the capacityof the channel [8].It is worth mentioning that, under an adversary that choosesthe worstcase
Z
based on
X
, the best rate obtained so far hasbeen approximately
m
−
nm
(
n
−
2
t
)
packets [5], [6]. Thus, if the adversary can be somehow forced to choose
Z
randomly(rather than in a worstcase fashion), then it is possible toincrease the rate by approximately
t
packets.
6
III. C
OHERENT
N
ETWORK
C
ODING
W
ITH A
S
HARED
K
EY
Let us now describe our keybased error control scheme forcoherent network coding. The key is used to select a random,fullrank matrix
H
∈ T
v
×
m
. For every
H
, let
C
H
⊆
F
n
×
mq
be a code with
d
R
(
C
H
) =
d > t
+
ρ
such that
XH
T
= 0
,for all
X
∈ C
H
. The transmitter selects a transmission matrix
X
∈ C
H
. The receiver, upon receiving
Y
, computes
S
=
YH
T
=
AXH
T
+
DZH
T
=
DZH
T
.
Without loss of generality, assume that
rank
DZ
=
t
and that
D
is in reduced column echelon (RCE) form. We deﬁne a
columntrapping failure
to be the event that
rank
ZH
T
<t
. Assume a columntrapping failure does not occur, i.e.,
rank
ZH
T
=
t
. Then
rank
S
=
t
. It follows that
S
can bewritten as
S
=
DE
, for some
E
∈
F
t
×
vq
. Recall that
D
is unique, since it is in RCE form. Thus, the receiver candetermine
D
. We call this strategy
column trapping
because
D
speciﬁes the
column space
of the error matrix
DZ
, whichis then
trapped
in
S
whenever
ZH
T
is fullrank.We now proceed with the decoding approach of Section IIC. From (3) we can write
r
ˆ
V
=
TY
=
TAX
+
TDZ
=
I
+ˆ
LI
T
U
0
X
+
TDZ.
Thus,
r
= (
I
+ˆ
LI
T
U
)
X
+
B
1
Z
and
ˆ
V
=
B
2
Z
, where
B
1
B
2
=
B
=
TD
. Note that
B
is known to the receiver. This impliesthat the error word
e
r
−
X
can be written as
e
=ˆ
LI
T
U
X
+
B
1
Z
=
ˆ
L B
1
I
T
U
X Z
=ˆ
B
˜
Z
where the matrix
ˆ
B
=
ˆ
LB
1
is
known
to the receiver.Under the terminology of [6], we would say that
µ
=
rank
ˆ
B
≤
ρ
+
t
erasures
have occurred (each erasure is theknowledge of one dimension of the column space of the error).In this case, by inputting
(
r,
ˆ
B
)
to the decoder of [6], we canguarantee that the decoding will be successful provided that
µ < d
, which is true by assumption.It remains to compute the probability of columntrappingfailure and determine the achievable rates.A practical way to select
H
and
C
H
is the following. Let
H
=
I
−
P
T
, where
P
is a random matrix uniformlydistributed on
F
(
m
−
v
)
×
vq
. Let
C
H
=
{
x
P I
, x
∈ C}
,where
C ⊆
F
n
×
(
m
−
v
)
q
is a code with
d
R
(
C
) =
d
. It followsthat
d
R
(
C
H
) =
d
and, moreover,
XH
T
=
x
P I
H
T
= 0
for all
X
∈ C
H
. Note that if
(
m
−
v
)
≥
n
and
C
is an MRDcode, then
log
q
C
H

= (
m
−
v
)(
n
−
d
+ 1)
.We now compute the probability of columntrapping failure,assuming that
H
is selected as discussed above.
Theorem 1:
The probability of failure of the proposedscheme is upper bounded by
P
f
<m
−
vq
1+
v
−
t
1
−
q
−
t
1
−
q
−
1
<
2(
m
−
v
)
q
1+
v
−
t
.
The proof of Theorem 1, while similar to the proofs in[8], is not a trivial extension of those results, since it requirescounting subspaces of a speciﬁc form. In particular, the proof must consider that the information about the shape of
H
isavailable to the adversary.There are two ways to interpret Theorem 1 from aninformationtheory perspective. First, we could ﬁx
m
,
n
and
v
=
t
, and take
q
→ ∞
in order to achieve a rate of exactly
m
−
tm
(
n
−
t
−
ρ
)
packets per transmission. Alternatively, wecould ﬁx
q
, take
v > t
and let
v
,
t
and
n
grow proportionallywith
m
→ ∞
in order to achieve a rate arbitrarily close to
m
−
tm
(
n
−
t
−
ρ
)
.In any case, Theorem 1 allows us to design a system witha desired probability of failure for any ﬁnite parameters.IV. R
ANDOM
N
ETWORK
C
ODING
W
ITH A
S
HARED
K
EY
In this section we describe our error control scheme for therandom network coding model deﬁned in Section IIB. Thescheme is very similar to that of Section IID: the encodingscheme is followed by a stage of matrix multiplication, whichis then reversed at the receiver. The remaining decoding stepsare identical.As before, we assume that the key is used to select arandom matrix
P
uniformly distributed on
F
(
m
−
v
)
×
vq
. Let
H
=
I
−
P
T
, let
T
H
=
I
0
P I
and note that
T
−
1
H
=
I
0
−
P I
.
For a data matrix
U
∈
F
(
n
−
v
)
×
(
m
−
n
)
q
, let thetransmission matrix be given by
X
=
0
v
×
v
0
v
×
(
n
−
v
)
0
v
×
(
m
−
n
)
0
(
n
−
v
)
×
v
I
(
n
−
v
)
×
(
n
−
v
)
U
T
H
.
Upon reception of
Y
, the receiver computes
ˆ
Y
=
YT
−
1
H
=
A
(
X
+
BZ
)
T
−
1
H
.
Let us use
B
1
,
B
2
,
Z
1
,
Z
2
and
Z
3
as deﬁned in Section IID.Observe that
ZT
−
1
H
=
ZH
T
Z
2
Z
3
. Thus,
A
−
1
ˆ
Y
=
XT
−
1
H
+
B
ZH
T
Z
2
Z
3
=
B
1
ZH
T
B
1
Z
2
B
1
Z
3
B
2
ZH
T
I
+
B
2
Z
2
U
+
B
2
Z
3
.
It can now be recognized that the remainder of the decodingprocess is identical to that of Section IID, only with
ZH
T
inplace of
Z
1
. In particular, we deﬁne an
errortrapping failure
to be the event that
rank
B
1
ZH
T
< t
. Assuming that theerror trapping is successful, it follows from Section IID thatthe receiver can easily extract
U
after computing
RRE
ˆ
Y
.The probability of failure is upper bounded by
P
f
<P
f
1
+
P
f
2
, where
P
f
1
=
P
[
rank
B
1
< t
]
and
P
f
2
=
P
[
rank
ZH
T
< t
]
. Using (4) and Theorem 1, we have that
P
f
<mq
1+
v
−
t
1
−
q
−
t
1
−
q
−
1
<
2
mq
1+
v
−
t
.
The same interpretation following Theorem 1 is applicablehere. In particular, by properly choosing
v
, we can achievea rate arbitrarily close to
m
−
nm
(
n
−
t
)
while maintaining anarbitrarily low probability of failure.
7
V. D
ISCUSSION
The main idea behind the scheme of sections III and IVis to prepend a codeword
x
∈
F
n
×
(
m
−
v
)
q
with a “hash”given by
xP
. This hash informs the receiver not only that anerror has occurred, but also precisely the column space of theerror, thereby increasing the error correction capability of thescheme. If this column space is chosen in a worstcase fashion,then exploiting this information requires the use of MRDcodes; otherwise, if the column space is chosen randomly, then
x
can be taken essentially as a data matrix padded with allzero rows. (To see the necessity of MRD codes in the formercase, simply take
B
1
= 0
in the scheme of Section IV.)In essence, the key effectively performs a
randomization
of the row space of the error. This is seen by the fact that
Z
1
isreplaced with
ZH
T
in the scheme of Section IV. Thus, eventhough the adversary can choose a worstcase row space (say,with
Z
1
= 0
), the key allows us to use the scheme of [6], justas if this row space were random.With respect to the column space of the error, one mightquestion which assumption is more realistic (or “safe”), if either a random or a worstcase one. We argue that it dependson the type of network code (whether it is coherent or random).In coherent network coding, the network code is completelydisclosed to the adversary; by choosing the edges in whichto inject corrupt packets, the adversary can effectively choose
D
(or
B
). On the other hand, knowing the network code (aswell as being able to choose the injection edges) is
strictlynecessary
for an adversary to be able to choose
B
. Butthis is impossible in random network coding, if the codingcoefﬁcients at the internal nodes are truly random and chosenontheﬂy; in other words, the network code will not have beenrealized before the transmission is complete (at which point
Y
will already have arrived at the receiver).A main contribution of this paper is to provide a keybasederror control scheme that does not rely on an arbitrarily large
q
. This contribution is important because a moderately smallﬁeld size is typically required for practical network codingapplications [10], [11]. In our scheme, the ﬁeld size
q
can befreely chosen by the application. Given
t
, one can choose
v
as the smallest value needed to achieve a desired probabilityof failure; then,
m
can be designed to give a good tradeoff between rate loss and packet size. For instance, using thepractical values of
q
= 256
,
m
= 1240
and
P
f
<
10
−
6
,we ﬁnd
v
≥
t
+ 3
. This implies that the rate loss for randomnetwork coding (as a fraction of the nominal rate without errorcorrection) is only
(
t
+3)
/n
, rather than
2
t/n
without a key.For coherent network coding, the improvement is even closerto half. This result should be compared to [4], [7]. For thesame rate and the same probability of failure (assuming thatthe upper bound in [4, Corollary 6] is tight), it is easy toshow that the ﬁeld size required for the schemes in [4], [7]must satisfy
log
2
q
≥ −
log
2
P
f
+ (4
n
+ 1)log
2
(
n
+ 5)
. Inparticular, for
P
f
<
10
−
6
and
n
≥
20
, this requires
q
≥
2
397
.A ﬁnal comment has to be made with respect to the sizeof the key. The matrix
P
consists of
v
(
m
−
v
)
F
q
symbols(almost
v
packets), which is rather large. As argued in [7],the scheme is still justiﬁed since the key is independent of the message and thus can be shared prior to the transmission(similarly to a onetime pad). Note, however, that we are notinterested in conﬁdentiality, but only in error control. Thus, itis not necessary for
P
to be truly random, but simply to look random to the adversary. In particular, we may choose the keyto be the seed of a pseudorandom number generator used togenerate
P
, and refresh the key once a round through a lowrate secret channel. In this case, the size of the key shouldroughly correspond to the desired probability of failure, i.e.,20 bits to maintain
P
f
<
2
−
20
.Note that an extension to multicast may decrease either therate (by requiring multiple hashes) or the security level (byhaving multiple receivers share the same key) and thereforeseems an interesting avenue for future work.VI. C
ONCLUSION
In this paper, we have presented an error control scheme fornetwork coding based on the assumption that transmitter andreceiver share a secret key. Our scheme relies on standard (notkeybased) error control schemes and works for both coherentand random network coding. The scheme can be seen as afeature that is added to the standard schemes, allowing toreduce by half the redundancy that would be required if akey were not used. When compared to previous keybasedapproaches, our scheme has the advantage of being simpler,more efﬁcient computationally, and applicable under mostpacket lengths and ﬁeld sizes. In particular, the scheme can beeasily applied on top of any existing network coding system.R
EFERENCES[1] N. Cai and R. W. Yeung, “Network error correction, part II: Lowerbounds,”
Commun. Inform. Syst.
, vol. 6, no. 1, pp. 37–54, 2006.[2] Z. Zhang, “Linear network error correction codes in packet networks,”
IEEE Trans. Inf. Theory
, vol. 54, no. 1, pp. 209–218, 2008.[3] D. Silva and F. R. Kschischang, “On metrics for error correction innetwork coding,” 2008, submitted for publication. [Online]. Available:http://arxiv.org/abs/0805.3824[4] S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard, andM. Effros, “Resilient network coding in the presence of byzantineadversaries,”
IEEE Trans. Inf. Theory
, vol. 54, no. 6, pp. 2596–2603,Jun. 2008.[5] R. K¨otter and F. R. Kschischang, “Coding for errors and erasures inrandom network coding,”
IEEE Trans. Inf. Theory
, vol. 54, no. 8, pp.3579–3591, Aug. 2008.[6] D. Silva, F. R. Kschischang, and R. K¨otter, “A rankmetric approachto error control in random network coding,”
IEEE Trans. Inf. Theory
,vol. 54, no. 9, pp. 3951–3967, 2008.[7] L. Nutman and M. Langberg, “Adversarial models and resilient schemesfor network coding,” in
Proc. IEEE Int. Symp. Information Theory
, 6–11July 2008, pp. 171–175.[8] D. Silva, F. R. Kschischang, and R. K¨otter, “Capacity of randomnetwork coding under a probabilistic error model,” 2008, submitted forpublication. [Online]. Available: http://arxiv.org/abs/0807.1372[9] S. Jaggi and M. Langberg, “Resilient network codes in the presenceof eavesdropping Byzantine adversaries,” in
Proc. IEEE Int. Symp. Information Theory
, 24–29 June 2007, pp. 541–545.[10] P. A. Chou, Y. Wu, and K. Jain, “Practical network coding,” in
Proc. Allerton Conf. on Comm., Control, and Computing
, Monticello, IL, Oct.2003, pp. 40–49.[11] M. Wang and B. Li, “
R
2
: Random push with random network codingin live peertopeer streaming,”
IEEE J. Sel. Areas Commun.
, vol. 25,no. 9, pp. 1655–1666, 2007.
8