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

Cryptography (94A60) Linear codes (general theory) (94B05) Decoding (94B35) Other types of codes (94B60) Bounds on codes (94B65) Applications of design theory to circuits and networks (94C30)

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

h o

packets, and wire-tap up to

m u

links, all throughout

e l l

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

e l l n^{p} r i m e - 2 t - h o - m u

packets for coherent communication, where

n^{p} r i m e

is the number of outgoing links at the source, for any packet length

m g e q n^{p} r i m e

(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 > e l l

, thus

q^{m} a p p r o x e l l^{n^{p} r i m e}

, which is always smaller than that of a Gabidulin code tailored for

e l l

shots, which would be at least

2^{e l l n^{p} r i m e}

. A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length

n = e l l n^{p} r i m e

, 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

m a t h c a l O (n^{p r i m e 4} e l l^{2} l o g (e l l)^{2})

operations in

m a t h b b F_{2}

.

Cited in

(23)

This page was built for publication: Reliable and Secure Multishot Network Coding Using Linearized Reed-Solomon Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224111)