Reliable and Secure Multishot Network Coding Using Linearized Reed-Solomon Codes

• Published in: IEEE transactions on information theory 2019-08, Vol.65 (8), p.4785-4803
• Main Authors: Martinez-Penas, Umberto, Kschischang, Frank R.
• Format: Article
• Language: English
• Subjects: Algorithms; Codes; Coding; Coherence; Communication; Complexity; Complexity theory; Decoding; Encoding; Fields (mathematics); Knowledge engineering; Knowledge management; Linearization; Linearized Reed-Solomon codes; Links; Multiplication; multishot network coding; Network coding; network error-correction; Network topologies; Packets (communication); Reed-Solomon codes; Reliability; sum-rank metric; sum-subspace codes; Wire; wire-tap channel; Wiretapping
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2019.2912165

Multishot network coding is considered in a worst-case adversarial setting in which an omniscient adversary with unbounded computational resources may inject erroneous packets in up to t links, erase up to \rho packets, and wire-tap up to \mu links, all throughout \ell shots of a linearly-coded network. Assuming no knowledge of the underlying linear network code (in particular, the network topology and underlying linear code may be random and change with time), a coding scheme achieving zero-error communication and perfect secrecy is obtained based on linearized Reed-Solomon codes. The scheme achieves the maximum possible secret message size of \ell n^\prime - 2t - \rho - \mu packets for coherent communication, where n^\prime is the number of outgoing links at the source, for any packet length m \geq n^\prime (largest possible range). By lifting this construction, coding schemes for non-coherent communication are obtained with information rates close to optimal for practical instances. The required field size is q^{m} , where q > \ell , thus q^{m} \approx \ell ^{n^\prime } , which is always smaller than that of a Gabidulin code tailored for \ell shots, which would be at least 2^{\ell n^\prime } . A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length n = \ell n^\prime , and which can be adapted to handle not only errors but also erasures, wire-tap observations and non-coherent communication. Combined with the obtained field size, the given decodi