Ressource en auto-formation : 4.7. Attack against Reed-Muller codes

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 Re...
cours / présentation - Création : 05-05-2015
Par : Irene MARQUEZ-CORBELLA, Nicolas SENDRIER, Matthieu FINIASZ
Partagez !

Présentation de: 4.7. Attack against Reed-Muller codes

Informations pratiques sur cette ressource

Langue du document : Anglais
Type : cours / présentation
Niveau : master, doctorat
Durée d'exécution : 5 minutes 48 secondes
Contenu : vidéo
Document : video/mp4
Poids : 151.71 Mo
Droits d'auteur : libre de droits, gratuit
Droits réservés à l'éditeur et aux auteurs. Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.

Description de la ressource en auto-formation

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)

Document(s) annexe(s) - 4.7. Attack against Reed-Muller codes

Partagez !

AUTEUR(S)

  • Irene MARQUEZ-CORBELLA
  • Nicolas SENDRIER
  • Matthieu FINIASZ

DIFFUSION

Cette ressource en auto-formation vous est proposée par :
Canal-U - accédez au site internet
Sur les réseaux sociaux :

EN SAVOIR PLUS

  • Identifiant de la fiche
    32951
  • Identifiant OAI-PMH
    oai:canal-u.fr:32951
  • Schéma de la métadonnée
  • Entrepôt d'origine
    Canal-U

Ressources en auto-formation sur les mêmes thèmes

Présentation de la ressource en auto-formation 4.9. Goppa codes still resist cours / présentation
4.9. Goppa codes still resist
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
Description : All the results that we have seen this week doesn't mean that code based cryptography is broken. So in this session we will see that Goppa code still resists to all these attacks. So recall that it is assumed that Goppa codes are pseudorandom, that is there exist no efficient distinguisher for ...
Présentation de la ressource en auto-formation 4.8. Attack against Algebraic Geometry codes cours / présentation
4.8. Attack against Algebraic Geometry codes
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
Description : In this session, we will present an attack against Algebraic Geometry codes (AG codes). Algebraic Geometry codes is determined by a triple. First of all, an algebraic curve of genus g, then a n-tuple of rational points and then a divisor which has disjoint support from the n-tuple P. Then, the A ...