Reliable and Secure Multishot Network Coding Using Linearized Reed-Solomon Codes
Umberto Martinez-Penas, Frank R. Kschischang · IEEE Transactions on Information Theory · 2019
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 p packets, and wire-tap up to μ links, all throughout I 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 ℓn' -2t -p -μ packets for coherent communication, where n' is the number of outgoing links at the source, for any packet length m ≥ n' (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 qm, where q > ℓ, thus qm≈ ℓn', which is always smaller than that of a Gabidulin code tailored for I shots, which would be at least 2ℓn'. A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length n = ℓn', and which can be adapted to handle not only errors but also erasures, wiretap observations and non-coherent communication. Combined with the obtained field size, the given decoding complexity is of O(n'4ℓ2log(ℓ)2) operations in F2, whereas the most efficient known decoding algorithm for a Gabidulin code has a complexity of O(n'3.69ℓ3.69log(ℓ)2) operations in F2, assuming a multiplication in a finite field F costs about log(|F|)2operations in F2.