Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Problem (PEP), in which isometries must be permutations. LEP and PEP have recently gained renewed interest as the security foundations for several post-quantum schemes, including LESS. A recent paper has introduced the use of the Schur product to solve PEP, identifying many new easy-to-solve instances. In this paper, we extend this result to LEP. In particular, we generalize the approach and rely on the more general notion of power codes. Combining it with Frobenius automorphisms and Hermitian hulls, we identify many classes of easy LEP instances. To the best of our knowledge, this is the first work exploiting algebraic weaknesses for LEP. Finally we show an improved reduction to PEP whenever the coefficients of the monomial matrix are in a subgroup of the multiplicative group of the finite field.

Abstract We investigate the asymptotic density of error-correcting codes with good distance properties and prescribed linearity degree, including (sub)linear and nonlinear codes. We focus on the general setting of finite translation-invariant metric spaces, and then specialize our results to the Hamming metric, to the rank metric, and to the sum-rank metric. Our results show that the asymptotic density of codes heavily depends on the imposed linearity degree and the chosen metric.

We determine the asymptotic proportion (or density) of free modules over finite chain rings with good distance properties and treat the asymptotics in the code length n and the residue field size q separately. We then specialize and apply our technique to rank metric codes and to Hamming metric codes.

For a prime power q, an integer m and 0 ≤ e ≤ m − 1 we study the e-Galois hull dimension of Gabidulin codes Gk(α) of length m and dimension k over ${\mathbb{F}_{{q^m}}}$. Using a self-dual basis α of ${\mathbb{F}_{{q^m}}}$ over ${\mathbb{F}_q}$, we first explicitly compute the hull dimension of Gk(α). Then a necessary and sufficient condition of Gk(α) to be linear complementary dual (LCD), self-orthogonal and self-dual will be provided. We prove the existence of e-Galois (where $e = \frac{m}{2}$) self-dual Gabidulin codes of length m for even q, which is in contrast to the known fact that Euclidean self-dual Gabidulin codes do not exist for even q. As an application, we construct two classes of MDS entangled-assisted quantum error-correcting codes (MDS EAQECCs) whose parameters have more flexibility compared to known codes in this context.

We propose reducible algebraic curves as a mechanism to construct partial maximum distance separable codes geometrically. We obtain new general existence results, new explicit constructions, and improved estimates on the smallest field sizes over which such codes can exist. Our results are obtained by combining ideas from projective algebraic geometry, combinatorics, and probability theory.

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.

Private information retrieval (PIR) schemes for coded storage with colluding servers are presented, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed, and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. In the special case of no server collusion, this rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems. While many PIR schemes in the literature require field sizes that grow with the number of servers and files in the system, we focus especially on the case of a binary base field, for which Reed-Muller codes serve as an important and explicit class of examples.

We consider data transmission over a network where each edge is an erasure channel and the inner nodes transmit the random linear combinations of their incoming information. We distinguish two channel models in this setting: the row and the column erasure channel model. For both models, we investigate spread codes and determine their symbol erasure correction capability and the probability of decoding success. We also compare the performance of spread codes to other known codes suitable for those models. Furthermore, we explain how to decode these codes in the two channel models and compare the decoding complexities. The results show that depending on the application and the to-be-optimized aspect, any combination of codes and channel models can be the best choice.

We would like to thank Mahdieh Hakimi Poroch and Ali Asghar Talebi for pointing out two errors inProposition 28andTheorem 29of the original paper[1]. The correct formulation for these two statements is as follows.

Cryptosystems based on rank metric codes have been considered as an alternative to McEliece cryptosystems due to the relative difficulty of solving the rank syndrome decoding problem. Generic attacks have recently seen several improvements, notably in the work of Gaborit et al., who give an improved algorithm using linearized polynomials which yields a polynomial time algorithm for certain parameters. On the structural side, many of the proposals for cryptosystems based on Gabidulin codes have proven to be weak, following an attack by Overbeck in 2001. Of the Gabidulin based systems managing to resist Overbeck's attack, several were recently broken by Horlemann-Trautmann et al. using an attack based on finding the elements of rank one in some extended code. In this paper, we extend the polynomial time algorithm of Gaborit using the same underlying idea as Horlemann-Trautmann et al., and then demonstrate how codes with implicit structural weakness may be exploited, even if the explicit structure is not determined. We use this attack to break a Gabidulin code based cryptosystem which has so far resisted structural attacks.

We introduce cross-packing lattices for Rician fading channels, motivated by a geometric interpretation stemming from the pairwise error probability analysis. We approximate the star bodies arising from the pairwise error probability analysis with n-dimensional crosses of radius t, consisting of 2nt + 1 unit cubes, for some positive integer t. We give a construction for a family of cross-packing lattices for all dimensions and any minimum cross distance 2t + 1. We show by simulations how our new cross-packing lattices perform compared to other known lattices over the Rician fading channel, for different values of the Rician K-factor.

This paper provides new constructions and lower bounds for subspace codes, using Ferrers diagram rank-metric codes from matchings of the complete graph and pending blocks. We present different constructions for constant dimension codes with minimum injection distance 2 or k - 1, where k is the constant dimension. Furthermore, we present a construction of new codes from old codes for any minimum distance. Then, we construct nonconstant dimension codes from these codes. Some examples of codes obtained by these constructions are the largest known codes for the given parameters.

Spread codes and orbit codes are special families of constant dimension subspace codes. These codes have been well-studied for their error correction capability and transmission rate, but the question of how to encode and retrieve messages has not been investigated. In this work we show how the message space can be chosen for a given code and how message encoding and retrieval can be done.

We show how Gabidulin codes can be list decoded by using an iterative parametrization approach. For a given received word, our decoding algorithm processes its entries one by one, constructing four polynomials at each step. This then yields a parametrization of interpolating solutions for the data so far. From the final result a list of all codewords that are closest to the received word with respect to the rank metric is obtained.

This paper provides new constructive lower bounds for constant dimension codes, using Ferrers diagram rank metric codes and pending blocks. Constructions for two families of parameters of constant dimension codes are presented. The examples of codes obtained by these constructions are the largest known constant dimension codes for the given parameters.

A constant dimension code consists of a set of k-dimensional subspaces of \BBF qn. Orbit codes are constant dimension codes which are defined as orbits of a subgroup of the general linear group, acting on the set of all subspaces of \BBF qn. If the acting group is cyclic, the corresponding orbit codes are called cyclic orbit codes. In this paper, we show how orbit codes can be seen as an analog of linear codes in the block coding case. We investigate how the structure of cyclic orbit codes can be utilized to compute the minimum distance and cardinality of a given code and propose different decoding procedures for a particular subclass of cyclic orbit codes.

Orbit codes are a family of codes applicable for communications on a random linear network coding channel. The paper focuses on the classification of these codes. We start by classifying the conjugacy classes of cyclic subgroups of the general linear group. As a result, we are able to focus the study of cyclic orbit codes to a restricted family of them.

We introduce a new class of constant dimension codes called orbit codes. The basic properties of these codes are derived. It will be shown that many of the known families of constant dimension codes in the literature are actually orbit codes.