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.
Intervenants
Thèmes
Notice
Documentation
Dans la même collection
-
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.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.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.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.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.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.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.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.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.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.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.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
-
-
An Introduction to Iris: Higher-Order Concurrent Separation LogicBirkedalLars
Modern programming languages such as Java, Scala, and Rust are examples of concurrent higher-order imperative programming languages.
-
Opinion polarization and network segregation. Modelling a complex RelationshipFlacheAndreas
Recently, many societies seem to shift towards more polarization and volatility in opinions, for example in attitudes about immigration, climate policy, or the best policy response to Covid-19. A
-
21 Molecular Algorithms Using Reprogrammable DNA Self-AssemblyWoodsDamien
The history of computing tells us that computers can be made of almost anything: silicon, gears and levers, neurons, flowing water, interacting particles or even light. Although lithographically
-
Topological insights in neuroscienceHess BellwaldKathryn
Over the past decade, and particularly over the past five years, research at the interface of topology and neuroscience has grown remarkably fast. Topology has, for example, been successfully applied
-
Quelques algorithmes de calcul d'enveloppe convexe en 2DGiraultAlain
Le calcul de l'enveloppe convexe d'un nuage de points est un des problèmes fondamentaux en informatique, avec des applications multiples : traitement d'images, reconstruction 3D, détection de
-
Modélisation de la croissance des micro-organismesJongHidde de
La croissance microbienne peut être formulée comme un problème d'optimisation : comment allouer les ressources nutritives extraites de l'environnement aux différentes fonctions cellulaires afin de
-
Les mathématiques et la physique dans les effets spéciaux et les jeux vidéoNeyretFabrice
La synthèse d’images (parfois appelée « la 3D ») permet de créer dans l’ordinateur des mondes fictifs, ultra-réalistes ou de style cartoon selon l’envie des graphistes, des réalisateurs, des
-
Théorie de l’appariement et applications actuelles
Pourquoi y a-t-il tant de personnes sans emploi alors qu’au même moment un grand nombre de postes sont disponibles ? La théorie de l’appariement analyse ces problèmes où un certain nombre de
-
Caches, montrez-vous !DurandMarie
Les processeurs actuels permettent de l'ordre de quelques tera-opérations par seconde. Puissance nécessaire pour soutenir les besoins en simulation numérique, qui constitue, après la théorie et l
-
Self-Supervised Visual Learning and SynthesisEfrosAlexei A.
Computer vision has made impressive gains through the use of deep learning models, trained with large-scale labeled data. However, labels require expertise and curation and are expensive to collect.
-
Theoretical Foundations for Runtime MonitoringAcetoLuca
Runtime monitoring/verification is a lightweight technique that complements other verification methods in a multi-pronged approach towards ensuring software correctness. The technique poses novel
