On the number of inequivalent Gabidulin codes

Maximum rank-distance (MRD) codes are extremal codes in the space of \(m\times n\) matrices over a finite field, equipped with the rank metric. Up to generalizations, the classical examples of such codes were constructed in the 1970s and are today known as Gabidulin codes. Motivated by several recent approaches to construct MRD codes that are inequivalent to Gabidulin codes, we study the equivalence issue for Gabidulin codes themselves. This shows in particular that the family of Gabidulin codes already contains a huge subset of MRD codes that are pairwise inequivalent, provided that \(2\leqslant m\leqslant n-2\).     

Generalized Gabidulin codes over fields of any characteristic

We generalize Gabidulin codes to a large family of fields, non necessarily finite, possibly with characteristic zero. We consider a general field extension and any automorphism in the Galois group of the extension. This setting enables one to give several definitions of metrics related to the rank-metric, yet potentially different. We provide sufficient conditions on the given automorphism to ensure that the associated rank metrics are indeed all equal and proper, in coherence with the usual definition from linearized polynomials over finite fields. Under these conditions, we generalize the notion of Gabidulin codes. We also present an algorithm for decoding errors and erasures, whose complexity is given in terms of arithmetic operations. Over infinite fields the notion of code alphabet is essential, and more issues appear that in the finite field case. We first focus on codes over integer rings and study their associated decoding problem. But even if the code alphabet is small, we have to deal with the growth of intermediate values. A classical solution to this problem is to perform the computations modulo a prime ideal. For this, we need study the reduction of generalized Gabidulin codes modulo an ideal. We show that the codes obtained by reduction are the classical Gabidulin codes over finite fields. As a consequence, under some conditions, decoding generalized Gabidulin codes over integer rings can be reduced to decoding Gabidulin codes over a finite field.     

Cardinal rank metric codes over Galois rings

In 1985, Gabidulin introduced the rank metric in coding theory over finite fields, and used this kind of codes in a McEliece cryptosystem, six years later. In this paper, we consider rank metric codes over Galois rings. We propose a suitable metric for codes over such rings, and show its main properties. With this metric, we define Gabidulin codes over Galois rings, propose an efficient decoding algorithm for them, and hint their cryptographic application.     

Severely denting the Gabidulin version of the McEliece Public Key Cryptosystem

Gabidulin has proposed a version of the McEliece Public Key Cryptosystem using what he calls maximum rank distance (MRD) codes in place of Goppa codes. It is shown how to break such a system by finding a trapdoor to it. For the size of code he suggests this can be done in about a week on a fast personal computer. The attack can be thwarted by increasing the size of the code, but the advantages claimed for the Gabidulin version over the McEliece version are then largely lost.     

How to Mask the Structure of Codes for a Cryptographic Use

In this paper we show how to strengthen public-key cryptosystems against known attacks, together with the reduction of the public-key. We use properties of subcodes to mask the structure of the codes used by the conceiver of the system. We propose new parameters for the cryptosystems and even a modified Niederreiter cryptosystem in the case of Gabidulin codes, with a public-key size of less than 4000 bits.Communicated by: P. WildAMS Classification: 11T71     

Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes

Encryption schemes based on the rank metric lead to small public key sizes of order of few thousands bytes which represents a very attractive feature compared to Hamming metric-based encryption schemes where public key sizes are of order of hundreds of thousands bytes even with additional structures like the cyclicity. The main tool for building public key encryption schemes in rank metric is the McEliece encryption setting used with the family of Gabidulin codes. Since the original scheme proposed in 1991 by Gabidulin, Paramonov and Tretjakov, many systems have been proposed based on different masking techniques for Gabidulin codes. Nevertheless, over the years most of these systems were attacked essentially by the use of an attack proposed by Overbeck. In 2005 Faure and Loidreau designed a rank-metric encryption scheme which was not in the McEliece setting. The scheme is very efficient, with small public keys of size a few kiloBytes and with security closely related to the linearized polynomial reconstruction problem which corresponds to the decoding problem of Gabidulin codes. The structure of the scheme differs considerably from the classical McEliece setting and until our work, the scheme had never been attacked. We show in this article that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim. Our work also shows that some parameters are not affected by our attack but at the cost of a lost of efficiency for the underlying schemes.     

Hierarchical erasure correction of linear codes

Linear codes over finite extension fields have widespread applications in theory and practice. In some scenarios, the decoder has a sequential access to the codeword symbols, giving rise to a hierarchical erasure structure. In this paper we develop a mathematical framework for hierarchical erasures over extension fields, provide several bounds and constructions, and discuss potential applications in distributed storage and flash memories. Our results show intimate connection to Universally Decodable Matrices, as well as to Reed-Solomon and Gabidulin codes.     

Linear codes using skew polynomials with automorphisms and derivations

In this work the definition of codes as modules over skew polynomial rings of automorphism type is generalized to skew polynomial rings, whose multiplication is defined using an automorphism and a derivation. This produces a more general class of codes which, in some cases, produce better distance bounds than module skew codes constructed only with an automorphism. Extending the approach of Gabidulin codes, we introduce new notions of evaluation of skew polynomials with derivations and the corresponding evaluation codes. We propose several approaches to generalize Reed-Solomon and BCH codes to module skew codes and for two classes we show that the dual of such a Reed-Solomon type skew code is an evaluation skew code. We generalize a decoding algorithm due to Gabidulin for the rank metric and derive families of Maximum Distance Separable and Maximum Rank Distance codes.     

Roos bound for skew cyclic codes in Hamming and rank metric

In this paper, a Roos like bound on the minimum distance for skew cyclic codes over a general field is provided. The result holds in the Hamming metric and in the rank metric. The proofs involve arithmetic properties of skew polynomials and an analysis of the rank of parity-check matrices. For the rank metric case, a way to arithmetically construct codes with a prescribed minimum rank distance, using the skew Roos bound, is also given. Moreover, some examples of MDS codes and MRD codes over finite fields are built, using the skew Roos bound.     

On transform-domain error and erasure correction by Gabidulin codes

Gabidulin codes are the rank metric analogues of Reed–Solomon codes and have found many applications including network coding. In this paper, we propose a transform-domain algorithm correcting both errors and erasures with Gabidulin codes. Interleaving or the direct sum of Gabidulin codes allows both decreasing the redundancy and increasing the error correcting capability for network coding. We generalize the proposed decoding algorithm for interleaved Gabidulin codes. The transform-domain approach allows to simplify derivations and proofs and also simplifies finding the error vector after solving the key equation.     

Classification of Extremal Double Circulant Formally Self-Dual Even Codes

Formally self-dual even codes have recently been studied. Double circulant even codes are a family of such codes and almost all known extremal formally self-dual even codes are of this form. In this paper, we classify all extremal double circulant formally self-dual even codes which are not self-dual. We also investigate the existence of near-extremal formally self-dual even codes.     

Structure Theorems for Group Ring Codes with an Application to Self-Dual Codes

Using ideas from the cohomology of finite groups, an isomorphism is established between a group ring and the direct sum of twisted group rings. This gives a decomposition of a group ring code into twisted group ring codes. In the abelian case the twisted group ring codes are (multi-dimensional) constacyclic codes. We use the decomposition to prove that, with respect to the Euclidean inner product, there are no self-dual group ring codes when the group is the direct product of a 2-group and a group of odd order, and the ring is a field of odd characteristic or a certain modular ring. In particular, there are no self-dual abelian codes over the rings indicated. Extensions of these results to non-Euclidean inner products are briefly discussed.     

Extension of Overbeck’s attack for Gabidulin-based cryptosystems

Cryptosystems based on codes in the rank metric were introduced in 1991 by Gabidulin, Paramanov, and Tretjakov (GPT) and have been studied as a promising alternative to cryptosystems based on codes in the Hamming metric. In particular, it was observed that the combinatorial solution for solving the rank analogy of the syndrome decoding problem appears significantly harder. Early proposals were often made with an underlying Gabidulin code structure. Gibson, in 1995, made a promising attack which was later extended by Overbeck in 2008 to cryptanalyze many of the systems in the literature. Improved systems were then designed to resist the attack of Overbeck and yet continue to use Gabidulin codes. In this paper, we generalize Overbeck’s attack to break the GPT cryptosystem for all possible parameter sets, and then extend the attack to cryptanalyze particular variants which explicitly resist the attack of Overbeck.     

Systematic maximum sum rank codes

In the last decade there has been a great interest in extending results for codes equipped with the Hamming metric to analogous results for codes endowed with the rank metric. This work follows this thread of research and studies the characterization of systematic generator matrices (encoders) of codes with maximum rank distance. In the context of Hamming distance these codes are the so-called Maximum Distance Separable (MDS) codes and systematic encoders have been fully investigated. In this paper we investigate the algebraic properties and representation of encoders in systematic form of Maximum Rank Distance (MRD) codes and Maximum Sum Rank Distance (MSRD) codes. We address both block codes and convolutional codes separately and present necessary and sufficient conditions for an encoder in systematic form to generate a code with maximum (sum) rank distance. These characterizations are given in terms of certain matrices that must be superregular in a extension field and that preserve superregularity after some transformations performed over the base field. We conclude the work presenting some examples of Maximum Sum Rank convolutional codes over small fields. For the given parameters the examples obtained are over smaller fields than the examples obtained by other authors.     

Asymptotically Good Codes from Generalized Algebraic-Geometry Codes

We consider generalized algebraic-geometry codes, based on places of the same degree of a fixed algebraic function field over a finite field. In this note, using a method similar to the Justesen’s one, we construct a family of such codes which is asymptotically good.Communicated by: D. Jangnickel     

Quantum twisted codes

A major contribution of [1] is a reduction of the problem of correcting errors in quantum computations to the construction of codes in binary symplectic spaces. This mechanism is known as the additive or stabilizer construction. We consider an obvious generalization of these quantum codes in the symplectic geometry setting and obtain general constructions using our theory of twisted BCH‐codes (also known as Reed–Solomon subspace subcodes). This leads to families of quantum codes with good parameters. Moreover, the generator matrices of these codes can be described in a canonical way. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 174–188, 2000     

Trellis Structure and Higher Weights of Extremal Self-Dual Codes

A method for demonstrating and enumerating uniformly efficient (permutation-optimal) trellis decoders for self-dual codes of high minimum distance is developed. Such decoders and corresponding permutations are known for relatively few codes.The task of finding such permutations is shown to be substantially simplifiable in the case of self-dual codes in general, and for self-dual codes of sufficiently high minimum distance it is shown that it is frequently possible to deduce the existence of these permutations directly from the parameters of the code.A new and tighter link between generalized Hamming weights and trellis representations is demonstrated: for some self-dual codes, knowledge of one of the generalized Hamming weights is sufficient to determine the entire optimal state complexity profile.These results are used to characterize the permutation-optimal trellises and generalized Hamming weights for all [32,16,8] binary self-dual codes and for several other codes. The numbers of uniformly efficient permutations for several codes, including the [24,12,8] Golay code and both [24,12,9] ternary self-dual codes, are found.     

Fast decoding of Gabidulin codes

Gabidulin codes are the analogues of Reed–Solomon codes in rank metric and play an important role in various applications. In this contribution, a method for efficient decoding of Gabidulin codes up to their error correcting capability is shown. The new decoding algorithm for Gabidulin codes (defined over ${\mathbb{F}_{q^m}}$ ) directly provides the evaluation polynomial of the transmitted codeword. This approach can be seen as a Gao-like algorithm and uses an equivalent of the Euclidean Algorithm. In order to achieve low complexity, a fast symbolic product and a fast symbolic division are presented. The complexity of the whole decoding algorithm for Gabidulin codes is ${\mathcal{O} (m^3 \, \log \, m)}$ operations over the ground field ${\mathbb{F}_q}$ .     

Improved cryptanalysis of rank metric schemes based on Gabidulin codes

We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck’s structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way corrects less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender. Consequently, an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometric transformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existing techniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed.