In this work, we introduce maximally recoverable codes with locality and availability. We consider locally repairable codes (LRCs) where certain subsets oftsymbols belong each toNlocal repair sets, which are pairwise disjoint after removing thetsymbols, and which are of sizer+ δ − 1 and can correct δ −1 erasures locally. Classical LRCs withNdisjoint repair sets and LRCs withN-availability are recovered when settingt= 1 andt= δ − 1 = 1, respectively. Allowingt> 1 enables our codes to reduce the storage overhead for the same locality and availability. In this setting, we define maximally recoverable LRCs (MR-LRCs) as those that can correct any globally correctable erasure pattern given the locality and availability constraints. We then identify a large class of global erasure patterns that can be corrected by such MR-LRCs and prove that they are all the correctable patterns whent= 1. We provide three explicit constructions of LRCs that can correct such erasure patterns (thus MR-LRCs fort= 1), based on MSRD codes, each attaining the smallest finite-field sizes for some parameter regime. Finally, we extend the known lower bound on finite-field sizes from classical MR-LRCs to our setting (for any value oft).

Abstract The problem of distributed matrix multiplication with straggler tolerance over finite fields is considered, focusing on field sizes for which previous solutions were not applicable (for instance, the field of two elements). We employ Reed-Muller-type codes for explicitly constructing the desired algorithms and study their parameters by translating the problem into a combinatorial problem involving sums of discrete convex sets. We generalize polynomial codes and matdot codes, discussing the impossibility of the latter being applicable for very small field sizes, while providing optimal solutions for some regimes of parameters in both cases.

Abstract In this work, we study linear codes with the folded Hamming distance, or equivalently, codes with the classical Hamming distance that are linear over a subfield. This includes additive codes. We study MDS codes in this setting and define quasi MDS (QMDS) codes and dually QMDS codes, which attain a more relaxed variant of the classical Singleton bound. We provide several general results concerning these codes, including restriction, shortening, weight distributions, existence, density, geometric description and bounds on their lengths relative to their field or alphabet sizes. We provide explicit examples and a binary construction with optimal lengths relative to their field or alphabet sizes, which beats any MDS code (in terms of length compared to the field or alphabet size).

The problem of straggler mitigation in distributed matrix multiplication (DMM) is considered for a large number of worker nodes and a fixed small finite field. Polynomial codes and matdot codes are generalized by making use of algebraic function fields (i.e., algebraic functions over an algebraic curve) over a finite field. The construction of optimal solutions is translated to a combinatorial problem on the Weierstrass semigroups of the corresponding algebraic curves. Optimal or almost optimal solutions are provided. These have the same computational complexity per worker as classical polynomial and matdot codes, and their recovery thresholds are almost optimal in the asymptotic regime (growing number of workers and a fixed finite field).

The problem of straggler mitigation in distributed matrix multiplication (DMM) is considered for a large number of worker nodes and a fixed small finite field. Polynomial codes and matdot codes are generalized by making use of algebraic function fields (i.e., algebraic functions over an algebraic curve) over a finite field. The construction of optimal solutions is translated to a combinatorial problem on the Weierstrass semigroups of the corresponding algebraic curves. Optimal or almost optimal solutions are provided. These have the same computational complexity per worker as classical polynomial and matdot codes, and their recovery thresholds are almost optimal in the asymptotic regime (growing number of workers and a fixed finite field).

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.

We construct six new explicit families of linear maximum sum-rank distance (MSRD) codes, each of which has the smallest field sizes among all known MSRD codes for some parameter regime. Using them and a previous result of the author, we provide two new explicit families of linear partial maximum distance separable (PMDS) codes with smaller field sizes than previous PMDS codes for some parameter regimes. Our approach is to characterize evaluation points that turn extended Moore matrices into the parity-check matrix of a linear MSRD code. We then produce such sequences from codes with good Hamming-metric parameters. The six new families of linear MSRD codes with smaller field sizes are obtained using MDS codes, Hamming codes, Bose--Chaudhuri--Hocquenghem codes, and three algebraic-geometry codes. The MSRD codes based on Hamming codes, of minimum sum-rank distance 3, meet a recent bound by Byrne, Gluesing-Luerssen, and Ravagnani [ IEEE Trans. Inform. Theory, 67 (2021), pp. 6456--6475].

Sum-rank metric codes have recently attracted the attention of many researchers, due to their relevance in several applications. Mathematically, the sum-rank metric is a natural generalization of both the Hamming metric and the rank metric. In this paper, we provide an Anticode Bound for the sum-rank metric, which extends the corresponding Hamming and rank-metric Anticode bounds. We classify then optimal anticodes, i.e., codes attaining the sum-rank metric Anticode Bound. We use these optimal anticodes to define generalized sum-rank weights and we study their main properties. In particular, we prove that the generalized weights of an MSRD code are determined by its parameters. As an application, in the Appendix we explain how generalized weights measure information leakage in multishot network coding.

In this work, cyclic-skew-cyclic codes and sum-rank BCH codes are introduced. Cyclic-skew-cyclic codes are characterized as left ideals of a suitable non-commutative finite ring, constructed using skew polynomials on top of polynomials (or vice versa). Single generators of such left ideals are found, and they are used to construct generator matrices of the corresponding codes. The notion of defining set is introduced, using pairs of roots of skew polynomials on top of poynomials. A lower bound (called sum-rank BCH bound) on the minimum sum-rank distance is given for cyclic-skew-cyclic codes whose defining set contains certain consecutive pairs. Sum-rank BCH codes, with prescribed minimum sum-rank distance, are then defined as the largest cyclic-skew-cyclic codes whose defining set contains such consecutive pairs. The defining set of a sum-rank BCH code is described, and a lower bound on its dimension is obtained. Thanks to it, tables are provided showing that sum-rank BCH codes beat previously known codes for the sum-rank metric for binary 2 ×2 matrices (i.e., codes whose codewords are lists of 2 ×2 binary matrices, for a wide range of list lengths that correspond to the code length). Finally, a decoder for sum-rank BCH codes up to half their prescribed distance is obtained.

Locally repairable convolutional codes (LRCCs) for distributed storage systems (DSSs) are introduced in this work. They enable local repair, for a single node erasure (or more generally, ∂ - 1 erasures per local group), and sliding-window global repair, which can correct erasure patterns with up to djc-1 erasures in every window of j + 1 consecutive blocks of n nodes, where djcis the jth column distance of the code. The parameter j can be adjusted, for a fixed LRCC, according to different catastrophic erasure patterns, requiring only to contact n(j + 1) - djc+1 nodes, plus less than μn other nodes, in the storage system, where μ is the memory of the code. A Singleton-type bound is provided for dcj. If it attains such a bound, an LRCC can correct the same number of catastrophic erasures in a window of length n(j + 1) as an optimal locally repairable block code of the same rate and locality, and with block length n(j + 1). In addition, the LRCC is able to perform the flexible and somehow local sliding-window repair by adjusting j. Furthermore, by adjusting and/or sliding the window, the LRCC can potentially correct more erasures in the original window of n(j + 1) nodes than an optimal locally repairable block code of the same rate and locality, and length n(j+1). Finally, the concept of partial maximum distance profile (partial MDP) codes is introduced. Partial MDP codes can correct all information-theoretically correctable erasure patterns for a given locality, local distance and information rate. An explicit construction of partial MDP codes whose column distances attain the provided Singleton-type bound, up to certain parameter j = L, is obtained based on known maximum sum-rank distance convolutional codes.

Information-theoretical private information retrieval (PIR) is considered from a coded database with colluding servers. The storage code is a locally repairable code (LRC) with maximal recoverability (MR), and in particular, with optimal global minimum distance, for arbitrary code parameters: Number of local groups g, locality r, local distance δ, dimension k ≤ gr and length n = g(r + δ - 1). Servers are identified bijectively with local groups, and only locally non-redundant information is considered and downloaded from each server, that is, only r nodes (out of r + δ - 1) are considered per server. When the remaining MDS code, after removing all locally redundant nodes, is a linearized Reed-Solomon code, a PIR scheme is provided achieving the (download) rate R = (N - k - rt + 1)/N, where N = gr = n - g(δ - 1) is the length of the restricted MDS code, for any t colluding servers such that k + rt ≤ N. The field size is roughly gr, polynomial in the number of servers g. Assume an arbitrarily large number of stored files. If N - k - rt = 0, the rate R = 1/N is the highest known and coincides with that of previous PIR schemes that work for any MDS storage code. If N - k - rt > 0, the achieved rate R > 1/N coincides with the best known rate of PIR schemes for MDS storage codes (but which do not work for LRCs or linearized Reed-Solomon storage codes) and is always strictly higher than that of known PIR schemes that work for arbitrary MDS storage codes.

Locally repairable convolutional codes (LRCCs) for distributed storage systems (DSSs) are introduced in this work. They enable local repair, for a single node erasure, and sliding-window global repair, which can correct up to djc-1 node erasures in a window of j+1 consecutive blocks of n nodes, where djcis the jth column distance of the code. The parameter j can be adjusted, for a fixed LRCC, according to different catastrophic erasure patterns, requiring only to contact n(j+1)-djc+1 nodes, plus less than μn other nodes, in the storage system, where μ is the memory of the code. A Singleton-type bound is provided for djc. If it attains such a bound, an LRCC can correct the same number of catastrophic erasures in a window of length n(j + 1) as an optimal locally repairable block code of the same rate and locality, and with block length n(j + 1), but being able to perform the flexible and somehow local sliding-window repair by adjusting j. Furthermore, by sliding the window to consider previous or consequent nodes without erasures, or by increasing the window size, the LRCC can potentially correct more erasures in the original window of n(j + 1) nodes than the optimal locally repairable block code. Finally, an explicit construction of LRCCs whose column distances attain the provided Singleton-type bound, up to certain parameter j = L, is obtained based on known maximum sum-rank distance convolutional codes.

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.

Locally repairable codes (LRCs) are considered with equal or unequal localities, local distances, and local field sizes. An explicit two-layer architecture with a sum-rank outer code is obtained, having disjoint local groups and achieving maximal recoverability (MR) for all families of local linear codes (MDS or not) simultaneously, up to a specified maximum locality$r $. Furthermore, the local linear codes (thus the localities, local distances, and local fields) can be efficiently and dynamically modified without global recoding or changes in architecture or outer code, while preserving the MR property, easily adapting to new configurations in storage or new hot and cold data. In addition, local groups and file components can be added, removed or updated without global recoding. The construction requires global fields of size roughly$g^{r} $, for$g $local groups and maximum or specified locality$r $. For equal localities, these global fields are smaller than those of previous MR-LRCs when$r \leq h $(global parities). For unequal localities, they provide an exponential field size reduction on all previous best known MR-LRCs. For bounded localities and a large number of local groups, the global erasure-correction complexity of the given construction is comparable to that of Tamo–Barg codes or Reed–Solomon codes with local replication, while local repair is as efficient as for the Cartesian product of the local codes. Reed–Solomon codes with local replication and Cartesian products are recovered from the given construction when$r=1 $and$h = 0 $, respectively. The given construction can also be adapted to provide hierarchical MR-LRCs for all types of hierarchies and parameters. Finally, subextension subcodes and sum-rank alternant codes are introduced to obtain further exponential field size reductions, at the expense of lower information rates.

Secret-sharing schemes with optimal and universal communication overheads have been obtained independently by Bitar et al. and Huang et al. However, their constructions require a finite field of size q n, where n is the number of shares, and do not provide strong security. In this paper, we give a general framework to construct communication efficient secretsharing schemes based on sequences of nested linear codes, which allows to use, in particular, algebraic geometry codes and allows to obtain strongly secure and communication-efficient schemes. Using this framework, we obtain: 1) schemes with universal and close to optimal communication overheads for arbitrarily large lengths n and a fixed finite field; 2) the first construction of schemes with universal and optimal communication overheads and optimal strong security (for restricted lengths), having, in particular, the component-wise security advantages of perfect schemes and the security and storage efficiency of ramp schemes; and 3) schemes with universal and close to optimal communication overheads and close to optimal strong security defined for arbitrarily large lengths n and a fixed finite field.

Universal security over a network with linear network coding has been intensively studied. However, previous linear codes and code pairs used for this purpose were linear over a larger field than that used on the network, which restricts the possible packet lengths of optimal universal secure codes, does not allow to apply known list-decodable rank-metric codes and requires performing operations over a large field. In this paper, we introduce new parameters (relative generalized matrix weights and relative dimension/rank support profile) for code pairs that are linear over the field used in the network, and show that they measure the universal security performance of these code pairs. For one code and non-square matrices, generalized matrix weights coincide with the existing Delsarte generalized weights, hence we prove the connection between these latter weights and secure network coding, which was left open. As main applications, the proposed new parameters enable us to: 1) obtain optimal universal secure linear codes on noiseless networks for all possible packet lengths, in particular for packet lengths not considered before, 2) obtain the first universal secure list-decodable rank-metric code pairs with polynomial-sized lists, based on a recent construction by Guruswami et al; and 3) obtain new characterizations of security equivalences of linear codes. Finally, we show that our parameters extend relative generalized Hamming weights and relative dimension/length profile, respectively, and relative generalized rank weights and relative dimension/intersection profile, respectively.

Reducible codes for the rank metric were introduced for cryptographic purposes. They have fast encoding and decoding algorithms, include maximum rank distance (MRD) codes, and can correct many rank errors beyond half of their minimum rank distance, which makes them suitable for error correction in network coding. In this paper, we study their security behavior against information leakage on networks when applied as coset coding schemes, giving the following main results: 1) we give lower and upper bounds on their generalized rank weights (GRWs), which measure worst case information leakage to the wire tapper; 2) we find new parameters for which these codes are MRD (meaning that their first GRW is optimal) and use the previous bounds to estimate their higher GRWs; 3) we show that all linear (over the extension field) codes, whose GRWs are all optimal for fixed packet and code sizes but varying length are reducible codes up to rank equivalence; and 4) we show that the information leaked to a wire tapper when using reducible codes is often much less than the worst case given by their (optimal in some cases) GRWs. We conclude with some secondary related properties: conditions to be rank equivalent to Cartesian products of linear codes and conditions to be rank degenerate, duality properties, and MRD ranks.

Rank weights and generalized rank weights have been proved to characterize error and erasure correction, and information leakage in linear network coding, in the same way as Hamming weights and generalized Hamming weights describe classical error and erasure correction, and information leakage in wire-tap channels of type II and code-based secret sharing. Although many similarities between both the cases have been established and proved in the literature, many other known results in the Hamming case, such as bounds or characterizations of weight-preserving maps, have not been translated to the rank case yet, or in some cases have been proved after developing a different machinery. The aim of this paper is to further relate both weights and generalized weights, show that the results and proofs in both cases are usually essentially the same, and see the significance of these similarities in network coding. Some of the new results in the rank case also have new consequences in the Hamming case.