Abstract Martínez-Peñas and Kschischang (IEEE Trans. Inf. Theory 65(8):4785–4803, 2019) proposed lifted linearized Reed–Solomon codes as suitable codes for error control in multishot network coding. We show how to construct and decode lifted interleaved linearized Reed–Solomon (LILRS) codes. Compared to the construction by Martínez-Peñas–Kschischang, interleaving allows to increase the decoding region significantly and decreases the overhead due to the lifting (i.e., increases the code rate), at the cost of an increased packet size. We propose two decoding schemes for LILRS that are both capable of correcting insertions and deletions beyond half the minimum distance of the code by either allowing a list or a small decoding failure probability. We propose a probabilistic unique Loidreau–Overbeck-like decoder for LILRS codes and an efficient interpolation-based decoding scheme that can be either used as a list decoder (with exponential worst-case list size) or as a probabilistic unique decoder. We derive upper bounds on the decoding failure probability of the probabilistic-unique decoders which show that the decoding failure probability is very small for most channel realizations up to the maximal decoding radius. The tightness of the bounds is verified by Monte Carlo simulations.

In this work, maximum sum-rank distance (MSRD) codes and linearized Reed-Solomon codes are extended to finite chain rings. It is proven that linearized Reed-Solomon codes are MSRD over finite chain rings, extending the known result for finite fields. For the proof, several results on the roots of skew polynomials are extended to finite chain rings. These include the existence and uniqueness of minimum-degree annihilator skew polynomials and Lagrange interpolator skew polynomials. A general cubic-complexity sum-rank Welch-Berlekamp decoder and a quadratic-complexity sum-rank syndrome decoder (under some assumptions) are then provided over finite chain rings. The latter also constitutes the first known syndrome decoder for linearized Reed–Solomon codes over finite fields. Finally, applications in Space-Time Coding with multiple fading blocks and physical-layer multishot Network Coding are discussed.

Mixed codes, which are error-correcting codes in the Cartesian product of different-sized spaces, model degrading storage systems well. While such codes have previously been studied for their algebraic properties (e.g., existence of perfect codes) or in the case of unbounded alphabet sizes, we focus on the case of finite alphabets, and generalize the Gilbert-Varshamov, sphere-packing, Elias-Bassalygo, and first linear programming bounds to that setting. In the latter case, our proof is also the first for the non-symmetric mono-alphabetic q-ary case using Navon and Samorodnitsky’s Fourier-analytic approach.

Abstract This paper considers coding for so-called partially stuck (defect) memory cells. Such memory cells can only store partial information as some of their levels cannot be used fully due to, e.g., wearout. First, we present new constructions that are able to mask u partially stuck cells while correcting at the same time t random errors. The process of “masking” determines a word whose entries coincide with writable levels at the (partially) stuck cells. For $$u>1$$ u > 1 and alphabet size $$q>2$$ q > 2 , our new constructions improve upon the required redundancy of known constructions for $$t=0$$ t = 0 , and require less redundancy for masking partially stuck cells than former works required for masking fully stuck cells (which cannot store any information). Second, we show that treating some of the partially stuck cells as erroneous cells can decrease the required redundancy for some parameters. Lastly, we derive Singleton-like, sphere-packing-like, and Gilbert–Varshamov-like bounds. Numerical comparisons state that our constructions match the Gilbert–Varshamov-like bounds for several code parameters, e.g., BCH codes that contain all-one word by our first construction.

Several cryptosystems based on the Ring Learning with Errors (RLWE) problem have been proposed within the NIST post-quantum cryptography standardization process, e.g., NewHope. Furthermore, there are systems like Kyber which are based on the closely related MLWE assumption. Both previously mentioned schemes result in a non-zero decryption failure rate (DFR). The combination of encryption and decryption for these kinds of algorithms can be interpreted as data transmission over a noisy channel. To the best of our knowledge this paper is the first work that analyzes the capacity of this channel. We show how to modify the encryption schemes such that the input alphabets of the corresponding channels are increased. In particular, we present lower bounds on their capacities which show that the transmission rate can be significantly increased compared to standard proposals in the literature. Furthermore, under the common assumption of stochastically independent coefficient failures, we give lower bounds on achievable rates based on both the Gilbert-Varshamov bound and concrete code constructions using BCH codes. By means of our constructions, we can either increase the total bitrate (by a factor of 1.84 for Kyber and by factor of 7 for NewHope) while guaranteeing the same DFR or for the same bitrate, we can significantly reduce the DFR for all schemes considered in this work (e.g., for NewHope from 2−216 to 2−12769).

Codes in the sum-rank metric have various applications in error control for multishot network coding, distributed storage and code-based cryptography. Linearized Reed-Solomon (LRS) codes contain Reed-Solomon and Gabidulin codes as subclasses and fulfill the Singleton-like bound in the sum-rank metric with equality. We propose the first known error-erasure decoder for LRS codes to unleash their full potential for multishot network coding by incorporating erasures into the known syndrome-based Berlekamp-Massey-like decoder. This allows to correct tFfull errors, tRrow erasures and tCcolumn erasures up to $2{t_F} + {t_R} + {t_C} \leq n - k$ in the sum-rank metric requiring at most $\mathcal{O}\left( {{n^2}} \right)$ operations in ${\mathbb{F}_{{q^m}}},$ where n is the code’s length and k its dimension. We show how the proposed decoder can be used to correct errors in the sum-subspace metric that occur in (noncoherent) multishot network coding.

This paper is concerned with list decoding of 2-interleaved binary alternant codes. The principle of the proposed algorithm is based on a combination of a list decoding algorithm for (interleaved) Reed-Solomon codes and an algorithm for (non-interleaved) alternant codes. A new upper bound on the decoding radius is derived and the list size is shown to scale polynomially in the code parameters. While it remains an open problem whether this upper bound is achievable, the provided simulation results show that a decoding radius exceeding the binary Johnson radius can be achieved with a high probability of decoding success by the proposed algorithm.

In this article, we present a new construction of evaluation codes in the Hamming metric, which we calltwisted Reed–Solomoncodes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results.

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.

Recently, Martínez-Peñas and Kschischang (IEEE Trans. Inf. Theory, 2019) showed that lifted linearized Reed-Solomon codes are suitable codes for error control in multishot network coding. We show how to construct and decode lifted interleaved linearized Reed-Solomon codes. Compared to the construction by Martínez-Peñas-Kschischang, interleaving allows to increase the decoding region significantly (especially w.r.t. the number of insertions) and decreases the overhead due to the lifting (i.e., increases the code rate), at the cost of an increased packet size. The proposed decoder is a list decoder that can also be interpreted as a probabilistic unique decoder. Although our best upper bound on the list size is exponential, we present a heuristic argument and simulation results that indicate that the list size is in fact one for most channel realizations up to the maximal decoding radius.

Locality enables storage systems to recover failed nodes from small subsets of surviving nodes. The setting where nodes are partitioned into subsets, each allowing for local recovery, is well understood. In this work we consider a generalization introduced by Gopalan et al., where, viewing the codewords as arrays, constraints are imposed on the columns and rows in addition to some global constraints. Specifically, we present a generic method of adding such global parity-checks and derive new results on the set of correctable erasure patterns. Finally, we relate the set of correctable erasure patterns in the considered topology to those correctable in tensor-product codes.

Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.

Power decoding is a partial decoding paradigm for arbitrary algebraic geometry codes for decoding beyond half the minimum distance, which usually returns the unique closest codeword, but in rare cases fails to return anything. The original version decodes roughly up to the Sudan radius, while an improved version decodes up to the Johnson radius, but has so far been described only for Reed-Solomon and one-point Hermitian codes. In this paper we show how the improved version can be applied to any algebraic geometry code.

This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity in the code length. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.

This paper presents an algorithm for decoding any linear interleaved code of high interleaving order in the rank metric. The new decoder is an adaptation of the Hamming-metric decoder by Metzner and Kapturowski (1990) and guarantees to correct all rank errors of weight up to$d-2$whose rank over the large base field of the code equals the number of errors, where$d$is the minimum rank distance of the underlying code. It is based on linear-algebraic computations, and has an explicit and easy-to-handle success condition.

Low-rank parity-check (LRPC) codes are rank-metric codes over finite fields, which have been proposed by Gaborit et al. (Proceedings of the workshop on coding and cryptography WCC, vol 2013, 2013) for cryptographic applications. Inspired by a recent adaption of Gabidulin codes to certain finite rings by Kamche et al. (IEEE Trans Inf Theory 65(12):7718-7735, 2019), we define and study LRPC codes over Galois rings-a wide class of finite commutative rings. We give a decoding algorithm similar to Gaborit et al.'s decoder, based on simple linear-algebraic operations. We derive an upper bound on the failure probability of the decoder, which is significantly more involved than in the case of finite fields. The bound depends only on the rank of an error, i.e., is independent of its free rank. Further, we analyze the complexity of the decoder. We obtain that there is a class of LRPC codes over a Galois ring that can decode roughly the same number of errors as a Gabidulin code with the same code parameters, but faster than the currently best decoder for Gabidulin codes. However, the price that one needs to pay is a small failure probability, which we can bound from above.

Abstract We propose the new rank-metric code-based cryptosystem which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. is an improved variant of the Faure–Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Talé Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail—hence resists the GOT attack. We also prove that the public-key encryption version of is IND-CPA secure in the standard model and the key encapsulation mechanisms version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of are short ciphertext sizes and (relatively) small key sizes. Further, guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented.

We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may eitherfailto return a codeword ormiscorrectto an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

Partial MDS (PMDS) and sector-disk (SD) codes are classes of erasure correcting codes that combine locality with strong erasure correction capabilities. We construct PMDS and SD codes with local regeneration where each local code is a bandwidth-optimal regenerating MDS code. In the event of a node failure, these codes reduce both, the number of servers that have to be contacted as well as the amount of network traffic required for the repair process. The constructions require significantly smaller field size than the only other construction known in literature. Further, we present a construction of PMDS codes with global regeneration which allow to efficiently repair patterns of node failures that exceed the local erasure correction capability of the code and thereby invoke repair across different local groups.

We study scalar-linear and vector-linear solutions of the generalized combination network. We derive new upper and lower bounds on the maximum number of nodes in the middle layer, depending on the network parameters and the alphabet size. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a lower bound and an upper bound on the gap in the alphabet size between optimal scalar-linear and optimal vector-linear network coding solutions. For a fixed network structure, while varying the number of middle-layer nodes r, the asymptotic behavior of the upper and lower bounds shows that the gap is in Θ(log(r)).

Partial MDS (PMDS) and sector-disk (SD) codes are classes of erasure codes that combine locality with strong erasure correction capabilities. We construct PMDS and SD codes where each local code is a bandwidth-optimal regenerating MDS code. The constructions require significantly smaller field size than the only other construction known in literature.

We study scalar-linear and vector-linear solutions to the generalized combination network. We derive new upper and lower bounds on the maximum number of nodes in the middle layer, depending on the network parameters. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a general lower bound on the gap in the alphabet size between scalar-linear and vector-linear solutions.

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders.

We define and analyze low-rank parity-check (LRPC) codes over extension rings of the finite chain ring Zpr, where p is a prime and r is a positive integer. LRPC codes have originally been proposed by Gaborit et al. (2013) over finite fields for cryptographic applications. The adaption to finite rings is inspired by a recent paper by Kamche et al. (2019), which constructed Gabidulin codes over finite principle ideal rings with applications to space-time codes and network coding. We give a decoding algorithm based on simple linear-algebraic operations. Further, we derive an upper bound on the failure probability of the decoder. The upper bound is valid for errors whose rank is equal to the free rank.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of decodable error matrices by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

TheLearningwithErrors(LWE) problem is considered to be a hard problem and lies the foundation of various cryptographic algorithms. Several cryptosystems based on the closely relatedRingLearningwithErrors(RLWE) problem have been proposed within the NIST PQC standardization process, e.g., the systems LAC and NewHope. The combination of encryption and decryption for these kinds of algorithms can be interpreted as data transmission over noisy channels. To the best of our knowledge this paper is the first work that analyzes the capacity of this channel. We extend this channel from binary toq-ary alphabets and show that this does not compromise the security of the related RLWE-based schemes if appropriate error correcting codes are used to prevent thedecryptionfailurerate(DFR) from increasing. We give a lower bound on the capacity of this channel showing that the achievable asymptotic rates are substantially (5.7 times for LAC and 10.7 times for NewHope) higher than the currently deployed ones for the finite length regime. Furthermore, under the assumption of stochastically independent coefficient failures, we show that substantially higher rates can also be achieved in the finite length setting by using the Gilbert-Varshamov bound. Moreover, we give explicit code constructions increasing the achievable rate by a factor of 2 for LAC and a factor of 7 for NewHope without increasing the DFR for the respective parameter sets achieving a security level equivalent to AES256.

Goppa Codes are a well-known class of codes with, among others, applications in code-based cryptography. In this paper, we present a collaborative decoding algorithm for interleaved Goppa codes (IGC). Collaborative decoding increases the decoding radius beyond half of the designed minimum distance. We consider wild Goppa codes and show that we can collaboratively correct more errors for binary Goppa codes than the Patterson decoder. We propose a modified version of the McEliece cryptosystem using wild IGC based on a recently proposed system by Elleuch et al., analyze attacks on the system and present some parameters with the corresponding key sizes.

We show that the sequence of dimensions of the linear spaces, generated by a given rank-metric code together with itself under several applications of a field automorphism, is an invariant for the whole equivalence class of the code. These invariants give rise to an easily computable criterion to check if two codes are inequivalent. With this criterion we then derive bounds on the number of equivalence classes of classical and twisted Gabidulin codes.

We study Reed-Solomon codes over arbitrary fields, inspired by several recent papers dealing with Gabidulin codes over fields of characteristic zero. Over the field of rational numbers, we derive bounds on the coefficient growth during encoding and the bit complexity of decoding, which is polynomial in the code length and in the bit width of error and codeword values. The results can be generalized to arbitrary number fields.

We show that the root-finding step in interpolation-based decoding of interleaved Gabidulin codes can be solved by finding a so-called minimal approximant basis of a matrix over a linearized polynomial ring. Based on existing fast algorithms for computing such bases over ordinary polynomial rings, we develop fast algorithms for computing them over linearized polynomials. As a result, root finding costs O~(ℓωM(n)) operations in Fqm, where ℓ is the interleaving degree, n the code length, Fqm the base field of the code, 2 ≤ ω ≤ 3 the matrix multiplication exponent, and M(n) ∈ O(n1.635) is the complexity of multiplying two linearized polynomials of degree at most n. This is an asymptotic improvement upon the previously fastest algorithm of complexity O(ℓ3n2), in some cases O(ℓ2n2).

In this work it is shown that locally repairable codes (LRCs) can be list-decoded efficiently beyond the Johnson radius for a large range of parameters by utilizing the local error-correction capabilities. The corresponding decoding radius is derived and the asymptotic behavior is analyzed. A general list-decoding algorithm for LRCs that achieves this radius is proposed along with an explicit realization for LRCs that are subcodes of Reed-Solomon codes (such as, e.g., Tamo-Barg LRCs). Further, a probabilistic algorithm of low complexity for unique decoding of LRCs is given and its success probability is analyzed. The second part of this work considers error decoding of LRCs and partial maximum distance separable (PMDS) codes through interleaved decoding. For a specific class of LRCs the success probability of interleaved decoding is investigated. For PMDS codes, it is shown that there is a wide range of parameters for which interleaved decoding can increase their decoding radius beyond the minimum distance such that the probability of successful decoding approaches 1 when the code length goes to infinity.

We present a generalisation of Twisted Reed-Solomon codes containing a new large class of MDS codes. We prove that the code class contains a large subfamily that is closed under duality. Furthermore, we study the Schur squares of the new codes and show that their dimension is often large. Using these structural properties, we single out a subfamily of the new codes which could be considered for code-based cryptography: These codes resist some existing structural attacks for Reed-Solomon-like codes, i.e. methods for retrieving the code parameters from an obfuscated generator matrix.

A repair of the Faure-Loidreau (FL) public-key code-based cryptosystem is proposed. The FL cryptosystem is based on the hardness of list decoding Gabidulin codes which are special rank-metric codes. We prove that the recent structural attack on the system by Gaborit et al. is equivalent to decoding an interleaved Gabidulin code. Since all known polynomial-time decoders for these codes fail for a large constructive class of error patterns, we are able to construct public keys that resist the attack. It is also shown that all other known attacks fail for our repair and parameter choices. Compared to other code-based cryptosystems, we obtain significantly smaller key sizes for the same security level.

We present a new general construction of MDS codes over a finite field Fq. We describe two explicit subclasses which contain new MDS codes of length at least q/2 for all values of q ≥ 11. Moreover, we show that most of the new codes are not equivalent to a Reed-Solomon code.

We define multi-block interleaved codes as codes that allow reading information from either a small sub-block or from a larger full block. The former offers faster access, while the latter provides better reliability. We specify the correction capability of the sub-block code through its gap t from optimal minimum distance, and look to have full-block minimum distance that grows with the parameter t. We construct two families of such codes when the number of sub-blocks is 3. The codes match the distance properties of known integrated-interleaving codes, but with the added feature of mapping the same number of information symbols to each sub-block. As such, they are the first codes that provide read access in multiple size granularities and correction capabilities.

We propose a new partial decoding algorithm for m-interleaved Reed-Solomon (IRS) codes that can decode, with high probability, a random error of relative weight 1 - Rm/m+1at all code rates R, in time polynomial in the code length n. For m > 2, this is an asymptotic improvement over the previous state-of-the-art for all rates, and the first improvement for R > 1/3 in the last 20 years. The method combines collaborative decoding of IRS codes with power decoding up to the Johnson radius.

This paper considers capacity and delay constraints for coded tunnels across an erasure channel which occurs on shared Internet satellite links. Such links are long latency bottlenecks with a limited memory input queue which drops packets when it overflows. The latency delays ARQ ACK feedback to senders, making it difficult for them to tune their packet transmission rate. This can cause the input queue to oscillate between empty and overflow. Queue oscillation leaves the link underutilised during the empty phases and slows down large packet flows. Channel coding can in principle provide goodput improvement in this scenario by letting senders accelerate to higher packet rates before burst losses occur and by mitigating exponential backoff after losses. However, this is only possible if the codes preserve sufficient spare channel transmission rate for the improved goodput to expand into. We formulate rate and delay constraints that such block codes must meet. Using loss data obtained on a purpose-built simulator network, we show that such coding is feasible in a practical scenario and that partial unit memory (PUM) codes are particularly suitable for this task. In this context, we propose a part-systematic encoding for PUM codes, which performs slightly better than non-systematic encoding.

Gabidulin codes, originally defined over finite fields, are an important class of rank metric codes with various applications. Recently, their definition was generalized to certain fields of characteristic zero and a Welch-Berlekamp like algorithm with complexity O(n3) was given. We propose a new application of Gabidulin codes over infinite fields: low-rank matrix recovery. Also, an alternative decoding approach is presented based on a Gao type key equation, reducing the complexity to at least O(n2). This method immediately connects the decoding problem to well-studied problems, which have been investigated in terms of coefficient growth and numerical stability.

This paper shows how to decode errors and erasures with Gabidulin codes in sub-quadratic time in the code length, improving previous algorithms which had at least quadratic complexity. The complexity reduction is achieved by accelerating operations on linearized polynomials. In particular, we present fast algorithms for division, multi-point evaluation and interpolation of linearized polynomials and show how to efficiently compute minimal subspace polynomials.