In this article, we investigate the decoding of the rank metric Reed–Muller codes introduced by Augot, Couvreur, Lavauzelle and Neri in 2021. These codes are defined from Abelian Galois extensions extending the construction of Gabidulin codes over arbitrary cyclic Galois extensions. We propose a polynomial time algorithm that rests on the structure of Dickson matrices, works on any such code and corrects any error of rank up to half the minimum distance.

We give a recursive decoding algorithm of the rank metric Reed-Muller codes introduced by Augot, Couvreur, Lavauzelle and Neri in 2021 for the binary case, i.e.,$\mathbf{G}= (\mathbb{Z} / 2 \mathbb{Z})^{m}$. In a broad range of parameters, this recursive decoding algorithm has better complexity compared to a recently proposed decoding algorithm based on Dickson matrices. Furthermore, imitating the recursive structure, we introduce a Plotkin-like construction of matrix rank metric codes over finite fields answering a long-standing open question. We also provide a decoding algorithm associated to this construction.

Tensor codes are a generalisation of matrix codes. Such codes are defined as subspaces of$r$-th order tensors for which the ambient space is endowed with the tensor-rank as a metric. A class of these codes was introduced by Roth, who outlined a decoding algorithm for low tensor-rank errors for particular cases. They may be viewed as a generalisation of the well-known Delsarte-Gabidulin-Roth maximum rank distance codes. We study a generalised class of these codes. We investigate the properties of these codes and outline decoding techniques for different metrics that leverage their tensor structure. We first consider a fibre-wise decoding approach, as each fibre of a codeword corresponds to a Gabidulin codeword. We then give a generalisation of Loidreau's decoding method that corrects errors with properties constrained by the dimensions of the slice-spaces and fibre-spaces. The metrics we consider are upper bounded by the tensor-rank metric, and therefore these algorithms also decode tensor-rank weight errors.11This work has emanated from research conducted with the financial support of the European Union MSCA Doctoral Networks, (HORIZON-MSCA-2021-DN-01, Project 101072316), the French Agence Nationale de la Recherche project ANR-21-CE39-0009-BARRACUDA and by Plan France 2030 ANR-22-PETQ-0008. Link to GitHub repository with programs:https://github.com/lucienfrancois/RothTensorCodes

We consider the decoding of rank metric codes assuming the error matrix is symmetric. We prove two results. First, for rates1/2, we propose a decoder for Gabidulin codes correcting symmetric errors of rank up to n – k. The two mentioned decoders are deterministic and worst case.

Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions$F$and$G$such that there exist two affine permutations$A$,$B$, and an affine function$C$satisfying$G = A \circ F \circ B + C$. While the problem has a simple formulation, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants:EA-partitioningdeals with partitioning a set of functions into disjoint EA-equivalence classes, andEA-recoveryis about recovering the tuple$(A,B,C)$if it exists. In this paper, we present a new algorithm that efficiently solves the EA-recovery problem for quadratic functions. Although its worst-case complexity occurs when dealing with APN functions, it supersedes, in terms of performance, all previously known algorithms for solving this problem for all quadratic functions and in any dimension, even in the case of APN functions. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. The best approach for EA-partitioning in practice mainly relies on class invariants. We provide an overview of the known invariants along with a new one based on theortho-derivative. This new invariant is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is very fast to compute, and it practically always distinguishes between EA-inequivalent quadratic APN functions.

This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed–Solomon codes,i.e.subcodes of Reed–Solomon codes over${\mathbb {F}_{q^{m}}}$whose entries lie in a fixed collection of${\mathbb {F}_{q}}$–subspaces of${\mathbb {F}_{q^{m}}}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called thetwisted productwhich yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen${\mathbb {F}_{q}}$–subspaces have dimension larger than$m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.

We revisit the seminal Brill-Noether algorithm in the rather generic situation of smooth divisors over a nodal plane projective curve. Our approach takes advantage of fast algorithms for polynomials and structured matrices. We reach sub-quadratic time for computing a basis of a Riemann-Roch space. This improves upon previously known complexity bounds.

We give polynomial time attacks on the McEliece public key cryptosystem-based either on algebraic geometry (AG) codes or on small co-dimensional subcodes of AG codes. These attacks consist in the blind reconstruction either of an error correcting pair (ECP), or an error correcting array (ECA) from the single data of an arbitrary generator matrix of a code. An ECP provides a decoding algorithm, that corrects up to ((d* - 1 - g)/2) errors, where d* denotes the designed distance and g denotes the genus of the corresponding curve, while with an ECA the decoding algorithm corrects up to ((d* - 1)/2) errors. Roughly speaking, for a public code of length n over Fq, these attacks run in O(n4log(n)) operations in Fqfor the reconstruction of an ECP and O(n5) operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to O(n3±ε log(n)) and O(n4±ε). Compared with the previous known attack due to Faure and Minder, our attack is efficient on codes from curves of arbitrary genus. Furthermore, we investigate how far these methods apply to subcodes of AG codes.

We present a polynomial-time structural attack against the McEliece system based on Wild Goppa codes defined over a quadratic finite field extension. We show that such codes can be efficiently distinguished from random codes. The attack uses this property to compute a filtration, that is to say, a family of nested subcodes which will reveal their secret algebraic description.

We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in O(n4) operations in Fq, where n denotes the code length. Compared to previous attacks, the present one allows to recover a decoding algorithm for the public key even for codes from high genus curves.

We study a construction of quantum LDPC codes proposed by MacKay, Mitchison, and Shokrollahi. It is based on the Cayley graph of \BBF2ntogether with a set of generators regarded as the columns of the parity-check matrix of a classical code. We give a general lower bound on the minimum distance of the quantum code in O(dn2) where d is the minimum distance of the classical code. This bound is logarithmic in the blocklength 2nof the quantum code. When the classical code is the [n,1,n] repetition code, we are able to compute the exact parameters of the associated quantum code which are [[2n, 2[(n+1)/2], 2[(n-1)/2]]].

We study a construction of Quantum LDPC codes proposed by MacKay, Mitchison and Shokrollahi in the draft [6]. It is based on the Cayley graph of F2ntogether with a set of generators regarded as the columns of the parity-check matrix of a classical code. We give a general lower bound on the minimum distance of the quantum code in O(dn2) where d is the minimum distance of the classical code. When the classical code is the [n, 1, n] repetition code, we are able to compute the exact parameters of the associated quantum code which are [[2n-1, 2 n/2, 2 n/2-1]].

We study the list-decoding problem of alternant codes (which includes obviously that of classical Goppa codes). The major consideration here is to take into account the (small) size of the alphabet. This amounts to comparing the generic Johnson bound to the q-ary Johnson bound. The most favourable case is q = 2, for which the decoding radius is greatly improved. Even though the announced result, which is the list-decoding radius of binary Goppa codes, is new, we acknowledge that it can be made up from separate previous sources, which may be a little bit unknown, and where the binary Goppa codes has apparently not been thought at. Only D. J. Bernstein has treated the case of binary Goppa codes in a preprint. References are given in the introduction. We propose an autonomous and simplified treatment and also a complexity analysis of the studied algorithm, which is quadratic in the blocklength n, when decoding e-away of the relative maximum decoding radius.

In this paper, new regular incidence structures are presented. They arise from sets of conics in the affine plane blown-up at its rational points. The LDPC codes given by these incidence matrices are studied. These sparse incidence matrices turn out to be redundant, which means that their number of rows exceeds their rank. Such a feature is absent from random LDPC codes and is in general interesting for the efficiency of iterative decoding. The performance of some codes under iterative decoding is tested. Some of them turn out to perform better than regular Gallager codes having similar rate and row weight.