Abstract In this note, we provide proven estimates for the complexity of the SupportMinors Modeling, mostly confirming the heuristic complexity estimates contained in the original article (Bardet (2020) Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Advances in cryptology. Springer, pp 507–536).

The MacWilliams' Extension Theorem is a classical result by Florence Jessie MacWilliams. It shows that every linear isometry between linear block-codes endowed with the Hamming distance can be extended to a linear isometry of the ambient space. Such an extension fails to exist in general for rank-metric codes, that is, one can easily find examples of linear isometries between rank-metric codes which cannot be extended to linear isometries of the ambient space. In this paper, we explore to what extent a MacWilliams' Extension Theorem may hold for rank-metric codes. We provide an extensive list of examples of obstructions to the existence of an extension, as well as a positive result.

Abstract It is well-known that the dimension of optimal anticodes in the rank-metric is divisible by the maximum m between the number of rows and columns of the matrices. Moreover, for a fixed k divisible by m, optimal rank-metric anticodes are the codes with least maximum rank, among those of dimension k. In this paper, we study the family of rank-metric codes whose dimension is not divisible by m and whose maximum rank is the least possible for codes of that dimension, according to the Anticode bound. As these are not optimal anticodes, we call them quasi optimal anticodes (qOACs). In addition, we call dually qOAC a qOAC whose dual is also a qOAC. We describe explicitly the structure of dually qOACs and compute their weight distributions, generalized weights, and associated q-polymatroids.

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Gröbner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo–Mumford regularity.

In 1997 Rosenthal and York defined generalized Hamming weights for convolutional codes, by regarding a convolutional code as an infinite dimensional linear code endowed with the Hamming metric. In this paper, we propose a new definition of generalized weights of convolutional codes, that takes into account the underlying module structure of the code. We derive the basic properties of our generalized weights and discuss the relation with the previous definition. We establish upper bounds on the weight hierarchy of MDS and MDP codes and show that, depending on the code parameters, some or all of the generalized weights of MDS codes are determined by the length, rank, and internal degree of the code. We also prove an anticode bound for convolutional codes and define optimal anticodes as the codes which meet the anticode bound. Finally, we classify optimal anticodes and compute their weight hierarchy.

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.

We propose an algebraic framework for end-to-end physical-layer network coding based on submodules transmission. Our approach is motivated by nested-lattice-based network coding schemes, that naturally induce end-to-end channels where the ambient space has the structure of a module over a principal ideal ring. The setup is compatible with previously proposed approaches for finite chain rings, and extends them to arbitrary principal ideal rings. We introduce a distance function between modules, and describe how it relates to information loss and errors. We also show that computing the distance between modules reduces to computing the length of certain ideals in the base ring. We then propose a definition of submodule error-correcting code, and establish two upper bounds for the cardinality of these codes. Finally, we present some constructions of submodule codes, showing that they have asymptotically optimal cardinality for certain choices of the parameters.

Optimal rank-metric codes in Ferrers diagrams are considered. Such codes consist of matrices having zeros at certain fixed positions and can be used to construct good codes in the projective space. First, we consider rank-metric anticodes and prove a code-anticode bound for Ferrers diagram rank-metric codes. The size of optimal linear anticodes is given. Four techniques and constructions of Ferrers diagram rank-metric codes are presented, each providing optimal codes for different diagrams and parameters for which no optimal solution was known before. The first construction uses maximum distance separable codes on the diagonals of the matrices, the second one takes a subcode of a maximum rank distance code, and the last two combine codes in small diagrams to a code in a larger diagram. The constructions are analyzed and compared, and unsolved diagrams are identified.

In this paper we introduce the class of spread codes for the use in random network coding. Spread codes are based on the construction of spreads in finite projective geometry. The major contribution of the paper is an efficient decoding algorithm of spread codes up to half the minimum distance.

In this work, we present a new structure for multiplication in finite fields. This structure is based on a digit-level LFSR (Linear Feedback Shift Register) multiplier, in which the area of the digit-multipliers is reduced using the Karatsuba method. We compare our results with the other works of the literature for F397. Furthermore, we propose new formulas for multiplication in F36.97. These new formulas reduce the number of F397-multiplications from 18 to 15. The finite fields F397and F36.97are important fields for pairing based cryptography.