Career

4 pages
50 views

A Key-Based Error Control Scheme for Network Coding

of 4
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
A Key-Based Error Control Scheme for Network Coding
Transcript
  A Key-Based 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 significantly higher than what can be achievedwithout a shared key. Moreover, differently from previous key-based approaches, the proposed scheme does not require the fieldsize 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 significant interest recently, and many quite differentapproaches have been proposed. The common model is thatof a matrix channel over a finite field, 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 worst-case 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 key-based approaches is thatthey rely on both the field 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. field size is not a reasonable assumption in practice and maypreclude a real-world implementation.In this paper, we present a key-based 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 field size or  the packetlength. In particular, real-world values for these parameters aresufficient 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. Sec-tion II introduces the channel models and review previous(not key-based) 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 finitefield F q and let T   n × m denote the set of all full-rank  n × m matrices over the same field. The n × m all-zero 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 978-1-4244-3401-5/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 specific sub-models: coherent network coding and noncoherent (more specifically, 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 simplifies the analysis considerably. C. Coherent Network Coding Without a Shared Key In this subsection we briefly 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 justifiedas 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 efficient implementationwhen C is a maximum-rank-distance (MRD) code. The log-cardinality of an MRD code, for m ≥ n , is given by log q |C| = m ( n − d + 1) . Thus, an efficient 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 II-B, 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 worst-case 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 worst-case 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 key-based error control scheme forcoherent network coding. The key is used to select a random,full-rank 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 define a column-trapping failure to be the event that rank ZH  T  <t . Assume a column-trapping 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 specifies the column space of the error matrix DZ  , whichis then trapped  in S  whenever ZH  T  is full-rank.We now proceed with the decoding approach of Sec-tion II-C. 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 column-trappingfailure 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 column-trapping 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 specific 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 aninformation-theory perspective. First, we could fix 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 fix 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 finite 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 defined in Section II-B. Thescheme is very similar to that of Section II-D: 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 defined in Section II-D.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 II-D, only with ZH  T  inplace of  Z  1 . In particular, we define an error-trapping failure to be the event that rank B 1 ZH  T  < t . Assuming that theerror trapping is successful, it follows from Section II-D 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 worst-case 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 all-zero 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 worst-case 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 worst-case 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 codingcoefficients at the internal nodes are truly random and chosenon-the-fly; 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 key-basederror control scheme that does not rely on an arbitrarily large q . This contribution is important because a moderately smallfield size is typically required for practical network codingapplications [10], [11]. In our scheme, the field 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 find 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 field 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 final 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 justified since the key is independent of the message and thus can be shared prior to the transmission(similarly to a one-time pad). Note, however, that we are notinterested in confidentiality, 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 pseudo-random 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 (notkey-based) 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 key-basedapproaches, our scheme has the advantage of being simpler,more efficient computationally, and applicable under mostpacket lengths and field 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 rank-metric 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 peer-to-peer streaming,” IEEE J. Sel. Areas Commun. , vol. 25,no. 9, pp. 1655–1666, 2007. 8
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x