4.7. Attack against Reed-Muller codes
- document 1 document 2 document 3
- niveau 1 niveau 2 niveau 3
- audio 1 audio 2 audio 3
Descriptif
In this session, we willintroduce an attack against binary Reed-Muller codes. Reed-Muller codes wereintroduced by Muller in 1954 and, later, Reed provided thefirst efficient decoding algorithm for these codes. Reed-Muller are just ageneralization of generalized Reed-Solomon codes. Generalized Reed-Solomoncodes are evaluation of univariate polynomials,and Reed-Muller codes are evaluation ofmultivariate polynomials. We will study binary Reed-Muller codes. The binary Reed-Mullerconsists of the set of codewords obtained by evaluating all theBoolean functions of degree r with m variables. Thus, theblock length of this code is 2^m. The dimension is anumber of polynomials of degree r with binary coefficient, andthe minimum distance is 2^m - r. Let us study two examples. The first example is aReed-Muller associated to the evaluation of all monomialsof degree 1 in three variables. The vectors associatedto these monomials are the following ones, which gives agenerator matrix of the code. This code has parameters:length 8, dimension 4, and minimum distance 4, thatis, it detects two errors and correct just one error.Take notice that the matrix of a Reed-Muller code withdegree bound 1 has a particular form. If we remove the firstrow, then we have at the i-th column just the number i-1read as a binary number. And this property willbe the key of the attack. Now, we have another example. We have the binaryReed-Muller code associated to the evaluation of monomialsof degree up to 2 in four variables. The vectorsassociated to this monomial are the following ones, which givea generator matrix of the code. This code has length 16,dimension 11, and minimum distance 4. Let us see someproperties of Reed-Muller code. First of all, we have thefollowing decreasing sequence. The code with the same degreebound as variables is the whole space. And moreover, the dual of aReed-Muller code is again a Reed-Muller code. And the proof is very easy.Just note that the dimension of the sum of these twocodes is 2^n, that is, the whole space. Moreover, the starproduct of these two codes is - this special code, which isthe code with all even weight vectors.
Intervenant
Thème
Notice
Documentation
Dans la même collection
-
4.9. Goppa codes still resistMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
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
-
4.8. Attack against Algebraic Geometry codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
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
-
4.6. Attack against GRS codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session we will discuss the proposal of using generalized Reed-Solomon codes for the McEliece cryptosystem. As we have already said, generalized Reed-Solomon codes were proposed in 1986 by
-
4.5. Error-Correcting PairsMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
We present in this session a general decoding method for linear codes. And we will see it in an example. Let C be a generalized Reed-Solomon code of dimension k associated to the pair (c, d). Then,
-
4.4. Attack against subcodes of GRS codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, we will talk about using subcodes of a Generalized Reed–Solomon code for the McEliece Cryptosystem. Recall that to avoid the attack of Sidelnikov and Shestakov, Berger and
-
4.2. Support Splitting AlgorithmMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
This session will be about the support splitting algorithm. For the q-ary case, there are three different notions of equivalence. The general one: two codes of length n are semi-linear equivalent
-
4.3. Distinguisher for GRS codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session we will see that generalized Reed-Solomon codes behave differently than random codes with respect to the star operation. Thus we can define a distinguisher for Generalized Reed
-
4.1. IntroductionMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
Welcome to the fourth week of the MOOC Code-based Cryptography. Recall that we have mainly two ways of cryptanalyzing in the McEliece cryptosystem. We have Message Attacks, which address the problem
Avec les mêmes intervenants
-
5.7. The Fast Syndrome-Based (FSB) Hash FunctionMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In the last session of this week, we will have a look at the FSB Hash Function which is built using the one-way function we saw in the previous session. What are the requirements for a
-
5.5. Stern’s Zero-Knowledge Identification SchemeMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, we are going to have a look at Stern’s Zero-Knowledge Identification Scheme. So, what is a Zero-Knowledge Identification Scheme? An identification scheme allows a prover to prove
-
5.6. An Efficient Provably Secure One-Way FunctionMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, we are going to see how to build an efficient provably secure one-way function from coding theory. As you know, a one-way function is a function which is simple to evaluate and
-
5.4. Parallel-CFSMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, I will present a variant of the CFS signature scheme called parallel-CFS. We start from a simple question: what happens if you try to use two different hash functions and compute
-
5.3. Attacks against the CFS SchemeMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, we will have a look at the attacks against the CFS signature scheme. As for public-key encryption, there are two kinds of attacks against signature schemes. First kind of attack is
-
5.2. The Courtois-Finiasz-Sendrier (CFS) ConstructionMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, I am going to present the Courtois-Finiasz-Sendrier Construction of a code-based digital signature. In the previous session, we have seen that it is impossible to hash a document
-
5.1. Code-Based Digital SignaturesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
Welcome to the last week of this MOOC on code-based cryptography. This week, we will be discussing other cryptographic constructions relying on coding theory. We have seen how to do public key
-
4.9. Goppa codes still resistMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
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
-
4.8. Attack against Algebraic Geometry codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
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
-
4.5. Error-Correcting PairsMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
We present in this session a general decoding method for linear codes. And we will see it in an example. Let C be a generalized Reed-Solomon code of dimension k associated to the pair (c, d). Then,
-
4.6. Attack against GRS codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session we will discuss the proposal of using generalized Reed-Solomon codes for the McEliece cryptosystem. As we have already said, generalized Reed-Solomon codes were proposed in 1986 by
-
4.4. Attack against subcodes of GRS codesMarquez-CorbellaIreneSendrierNicolasFiniaszMatthieu
In this session, we will talk about using subcodes of a Generalized Reed–Solomon code for the McEliece Cryptosystem. Recall that to avoid the attack of Sidelnikov and Shestakov, Berger and
Sur le même thème
-
Inauguration de l'exposition - Vanessa Vitse : Nombres de Sophie Germain et codes secretsVitseVanessa
Exposé de Vanessa Vitse (Institut Fourier) : Nombres de Sophie Germain et codes secrets
-
"Le mathématicien Petre (Pierre) Sergescu, historien des sciences, personnalité du XXe siècle"HerléaAlexandre
Alexandre HERLEA est membre de la section « Sciences, histoire des sciences et des techniques et archéologie industrielle » du CTHS. Professeur émérite des universités, membre effectif de l'Académie
-
Retour d'expérience sur l'utilisation croisée de plusieurs archives de fouillesTufféryChristophe
Dans le cadre d'une thèse de doctorat engagée depuis 2019, une étude historiographique et épistémologique des effets des dispositifs numériques sur l'archéologie et sur les archéologues au cours des
-
Information Structures for Privacy and FairnessPalamidessiCatuscia
Information Structures for Privacy and Fairness
-
Le Creativ’Lab, au cœur de la robotique et de l’intelligence artificielle (ASR N°18 - LORIA)HénaffPatrickLefebvreSylvain
Le LORIA, laboratoire phare de la Grande Région dans le domaine de l’informatique, propose de rendre la recherche plus ouverte, plus collaborative, plus ambitieuse… en un mot, plus créative, à travers
-
AI and Human Decision-Making: An Interdisciplinary PerspectiveCastellucciaClaude
This seminar will talk about some of the privacy risks of these systems and will describe some recent attacks. It will also discuss why they sometimes fail to deliver. Finally, we will also show that
-
Webinaire sur la rédaction des PGDLouvetViolaine
Rédaction des Plans de Gestion de Données (PGD) sous l’angle des besoins de la communauté mathématique.
-
Les algorithmes de Parcoursup
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Algorithmes d'aide à la décision publique / Ouverture
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Quelques enjeux autour des algorithmes d'aide à la décision publique
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Un nouveau système de répartition des greffons cardiaques utilisant un algorithme
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Règles, calcul et politique : investigation des choix de programmation inaperçus pour les aides au …
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
