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

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 $\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\ge 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 decoding complexity is of $\mathcal{O}(n^{\prime 4}{\ell }^2\log (\ell {)}^2)$ operations in ${\mathbb{F}}_2$.

References in corpus (10)

• A Rank-Metric Approach to Error Control in Random Network Coding
• Universal Secure Network Coding via Rank-Metric Codes
• On Metrics for Error Correction in Network Coding
• Relative Generalized Rank Weight of Linear Codes and Its Applications to Network Coding
• Bounds on List Decoding of Rank-Metric Codes
• Refined Coding Bounds and Code Constructions for Coherent Network Error Correction
• Fast Encoding and Decoding of Gabidulin Codes
• Convolutional Codes in Rank Metric with Application to Random Network Coding
• Multishot Codes for Network Coding: Bounds and a Multilevel Construction
• Relative generalized matrix weights of matrix codes for universal security on wire-tap networks

Cited by in corpus (5)

• Locally Repairable Convolutional Codes with Sliding Window Repair
• Network Coding-based Routing and Spectrum Allocation in Elastic Optical Networks for Enhanced Physical Layer Security
• Error-Erasure Decoding of Linearized Reed-Solomon Codes in the Sum-Rank Metric
• Distinguishing and Recovering Generalized Linearized Reed-Solomon Codes
• Fast Decoding of Interleaved Linearized Reed-Solomon Codes and Variants