Minimal codewords in Reed–Muller codes

Minimal codewords were introduced by Massey (Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pp 276–279, 1993) for cryptographical purposes. They are used in particular secret sharing schemes, to model the access structures. We study minimal codewords of weight smaller than 3 · 2 ^m−r in binary Reed–Muller codes RM(r, m) and translate our problem into a geometrical one, using a classification result of Kasami and Tokura (IEEE Trans Inf Theory 16:752–759, 1970) and Kasami et al. (Inf Control 30(4):380–395, 1976) on Boolean functions. In this geometrical setting, we calculate numbers of non-minimal codewords. So we obtain the number of minimal codewords in the cases where we have information about the weight distribution of the code RM(r, m). The presented results improve previous results obtained theoretically by Borissov et al. (Discrete Appl Math 128(1), 65–74, 2003), and computer aided results of Borissov and Manev (Serdica Math J 30(2-3), 303–324, 2004). This paper is in fact an extended abstract. Full proofs can be found on the arXiv.     

Projective Reed–Muller type codes on rational normal scrolls

In this paper we study an instance of projective Reed–Muller type codes, i.e., codes obtained by the evaluation of homogeneous polynomials of a fixed degree in the points of a projective variety. In our case the variety is an important example of a determinantal variety, namely the projective surface known as rational normal scroll, defined over a finite field, which is the basic underlining algebraic structure of this work. We determine the dimension and a lower bound for the minimum distance of the codes, and in many cases we also find the exact value of the minimum distance. To obtain the results we use some methods from Gröbner bases theory.     

On low weight codewords of generalized affine and projective Reed–Muller codes

We propose new results on low weight codewords of affine and projective generalized Reed–Muller (GRM) codes. In the affine case we prove that if the cardinality of the ground field is large compared to the degree of the code, the low weight codewords are products of affine functions. Then, without this assumption on the cardinality of the field, we study codewords associated to an irreducible but not absolutely irreducible polynomial, and prove that they cannot be second, third or fourth weight depending on the hypothesis. In the projective case the second distance of GRM codes is estimated, namely a lower bound and an upper bound on this weight are given.     

On Trellis Structures for Reed–Muller Codes

We study trellises of Reed–Muller codes from first principles. Our approach to local trellis behaviour seems to be new and yields amongst other things another proof of a result of Berger and Be'ery on the state complexity of Reed–Muller codes. We give a general form of a minimal-span generator matrix for the family of Reed–Muller codes with their standard bit-order. We apply this to determining the number of parallel subtrellises in any uniform sectionalisation of a Reed–Muller code and to designing trellises for Reed–Muller codes with more parallel subtrellises than the minimal trellis, but with the same state complexity.     

Simple algorithms for decoding systematic Reed–Solomon codes

A simple algorithm for decoding nonsystematic Reed–Solomon codewords was proposed by A. Shiozaki and independently by S. Gao. We first exhibit the companion algorithm for decoding systematic Reed–Solomon codes. Next, we improve this algorithm into one that is identical to traditional Reed–Solomon decoding. The algorithm will then be adjusted to work with nonstandard Reed–Solomon codes. Finally, we modify the algorithm into one that decodes Reed–Solomon codes with erasures that is slightly more efficient than existing techniques.     

Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes

Because of their interesting algebraic properties, several authors promote the use of generalized Reed–Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed–Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et al. which hides the generalized Reed–Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed–Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed–Solomon code.     

A new proof of Delsarte,Goethals and Mac Williams theorem on minimal weight codewords of generalized Reed–Muller codes

We give a new proof of Delsarte, Goethals and Mac Williams theorem on minimal weight codewords of generalized Reed–Muller codes published in 1970. To prove this theorem, we consider the intersection of the support of minimal weight codewords with affine hyperplanes and we proceed by recursion.     

Decoding interleaved Reed–Solomon codes beyond their joint error-correcting capability

A new probabilistic decoding algorithm for low-rate interleaved Reed–Solomon (IRS) codes is presented. This approach increases the error correcting capability of IRS codes compared to other known approaches (e.g. joint decoding) with high probability. It is a generalization of well-known decoding approaches and its complexity is quadratic with the length of the code. Asymptotic parameters of the new approach are calculated and simulation results are shown to illustrate its performance. Moreover, an upper bound on the failure probability is derived.     

The dimension of subcode-subfields of shortened generalized Reed–Solomon codes

Reed–Solomon (RS) codes are among the most ubiquitous codes due to their good parameters as well as efficient encoding and decoding procedures. However, RS codes suffer from having a fixed length. In many applications where the length is static, the appropriate length can be obtained from an RS code by shortening or puncturing. Generalized Reed–Solomon (GRS) codes are a generalization of RS codes, whose subfield-subcodes (SFSC) are extensively studied. In this paper we show that a particular class of GRS codes produces many SFSC with large dimension. We present two algorithms for searching through these codes and a list of new best-known codes obtained.     

New quantum MDS codes with large minimum distance and short length from generalized Reed–Solomon codes

Quantum maximum-distance-separable (MDS) codes are an important class of quantum codes. In this paper we mainly use classical Hermitian self-orthogonal generalized Reed–Solomon codes to construct three classes of new quantum MDS codes. Further, these quantum MDS codes have large minimum distance and short length.     

Reed‐muller codes: an ideal theory approach

By using techniques from commutative algebra such as the ideal of a set of points, the a‐invariant, the Hilbert function, and the Koszul complex, the main results about the Generalized and Projective Reed‐Muller codes are obtained.     

On Lagrangian–Grassmannian codes

Using the Lagrangian–Grassmannian, a smooth algebraic variety of dimension n(n + 1)/2 that parametrizes isotropic subspaces of dimension n in a symplectic vector space of dimension 2n, we construct a new class of linear codes generated by this variety, the Lagrangian–Grassmannian codes. We explicitly compute their word length, give a formula for their dimension and an upper bound for the minimum distance in terms of the dimension of the Lagrangian–Grassmannian variety.