Informations pratiques

Description de la ressource

Résumé

In this session, we will introduce an attack against binary Reed-Muller codes. Reed-Muller codes were introduced by Muller in 1954 and, later, Reed provided the first efficient decoding algorithm for these codes. Reed-Muller are just a generalization of generalized Reed-Solomon codes. Generalized Reed-Solomon codes are evaluation of univariate polynomials, and Reed-Muller codes are evaluation of multivariate polynomials. We will study binary Reed-Muller codes. The binary Reed-Muller consists of the set of codewords obtained by evaluating all the Boolean functions of degree r with m variables. Thus, the block length of this code is 2^m. The dimension is a number of polynomials of degree r with binary coefficient, and the minimum distance is 2^m - r. Let us study two examples. The first example is a Reed-Muller associated to the evaluation of all monomials of degree 1 in three variables. The vectors associated to these monomials are the following ones, which gives a generator matrix of the code. This code has parameters: length 8, dimension 4, and minimum distance 4, that is, it detects two errors and correct just one error. Take notice that the matrix of a Reed-Muller code with degree bound 1 has a particular form. If we remove the first row, then we have at  the i-th column just the number i-1 read as a binary number. And this property will be the key of the attack. Now, we have another example. We have the binary Reed-Muller code associated to the evaluation of monomials of degree up to 2 in four variables. The vectors associated to this monomial are the following ones, which give a generator matrix of the code. This code has length 16, dimension 11, and minimum distance 4. Let us see some properties of Reed-Muller code. First of all, we have the following decreasing sequence. The code with the same degree bound as variables is the whole space. And moreover, the dual of a Reed-Muller code is again a Reed-Muller code. And the proof is very easy. Just note that the dimension of the sum of these two codes is 2^n, that is, the whole space. Moreover, the star product of these two codes is  - this special code, which is the code with all even weight vectors.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Domaine(s)

• Cette ressource fait partie de
  • 4: Key Attacks