| Title | Reliable and Secure Multishot Network Coding using Linearized Reed-Solomon Codes |
| Publication Type | Conference Paper |
| Year of Publication | 2018 |
| Authors | Martínez-Peñas, Umberto, Kschischang, Frank R. |
| Conference Name | 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) |
| Keywords | coding scheme, composability, computational complexity, cyber physical systems, Decoding, encoding, error correction codes, inject erroneous packets, Knowledge engineering, linear codes, linear network code, linearized Reed-Solomon codes, multishot network coding, network coding, network error-correction, Network topology, Predictive Metrics, pubcrawl, random codes, Reed-Solomon codes, reliability, reliable multishot network coding, Resiliency, secure multishot network coding, sum-rank metric, sum-subspace codes, telecommunication network topology, telecommunication security, unbounded computational resources, wire-tap channel, worst-case adversarial setting, zero-error communication |
| Abstract | 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 r packets, and wire-tap up to m links, all throughout l shots of a (random) linearly-coded network. Assuming no knowledge of the underlying linear network code (in particular, the network topology and underlying linear code may 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 ln'-2t-r-m packets, where n' is the number of outgoing links at the source, for any packet length m n' (largest possible range), with only the restriction that l\textbackslashtextless;q (size of the base field). By lifting this construction, coding schemes for non-coherent communication are obtained with information rates close to optimal for practical instances. A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length n = ln', and which can be adapted to handle not only errors, but also erasures, wire-tap observations and non-coherent communication. |
| DOI | 10.1109/ALLERTON.2018.8635644 |
| Citation Key | martinez-penas_reliable_2018 |
Reliable and Secure Multishot Network Coding using Linearized Reed-Solomon Codes