Vidéo pédagogique

# 4.6. Attack against GRS codes

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
• document 1 document 2 document 3
• niveau 1 niveau 2 niveau 3
• audio 1 audio 2 audio 3
Descriptif

In this session we willdiscuss the proposal of using generalized Reed-Solomon codesfor the McEliece cryptosystem. As we have already said,generalized Reed-Solomon codes were proposed in1986 by Niederreiter. Recall that these codes areMDS, that is, they attain the maximum error correctingcapacity which is interpreted as shorter keys for thesame level of security. Moreover, these codes haveefficient decoding algorithms so they are suitablecandidates for code-based cryptography. But this proposal issubject to a polynomial attack by Sidelnikov-Shestakov. Take notice that if we knowa generalized Reed-Solomon code associated to the pair(a,b) of dimension k and dimension k - 1, that iswe know two codes, then by solving the followingsystem, we can obtain the generalized Reed-Solomoncode of dimension k - 2. And the proof is very easy. Just take notice that thestar product of the known codes provide the square code ofthe generalized Reed-Solomon code of dimension k - 1. In other words, a polynomial of degree at most k-1times a polynomial of degree at most k, yields to apolynomial of degree at most 2k - 2. And this property can beused iteratively to build the following decreasing sequence. Note that the generalizedReed-Solomon code of dimension 1 is the set ofmultiples of the vector b. Thus we can retrievethe vector b and then by solving a linearsystem, we can obtain also a. However, from the McEliececryptosystem, just a generator matrix of the generalizedReed-Solomon code of dimension k is known. And we will explain inthis slide how to compute a generator matrix of thesame generalized Reed-Solomon code by dropping byone the dimension. Recall that the shortenof a generalized Reed-Solomon code is again ageneralized Reed-Solomon code. Moreover, the code locatorof the shortened code is again the same code locator butrestricted to some coordinates. In particular shortening atthe first position we get a new generalized Reed-Solomon code, associated to the same code locator withoutthe first coordinate, and it is easy to get a generatormatrix of such shortened code: we just apply GaussianElimination to our matrix.

Intervenants
Thèmes
Notice
Sous-titrage
Anglais
Langue :
Anglais
Conditions d'utilisation
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.
Citer cette ressource:
Inria. (2015, 5 mai). 4.6. Attack against GRS codes. [Vidéo]. Canal-U. https://www.canal-u.tv/92787. (Consultée le 20 mai 2022)
Contacter
Documentation

## Dans la même collection

• Vidéo pédagogique
00:04:03
4.9. Goppa codes still resist
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:06:45
4.8. Attack against Algebraic Geometry codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:05:47
4.7. Attack against Reed-Muller codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:05:31
4.5. Error-Correcting Pairs
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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,

• Vidéo pédagogique
00:03:56
4.4. Attack against subcodes of GRS codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:06:20
4.2. Support Splitting Algorithm
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:05:18
4.3. Distinguisher for GRS codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:04:46
4.1. Introduction
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:08:21
5.7. The Fast Syndrome-Based (FSB) Hash Function
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:05:20
5.6. An Efficient Provably Secure One-Way Function
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:04:41
5.4. Parallel-CFS
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:07:11
5.5. Stern’s Zero-Knowledge Identification Scheme
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:04:51
5.3. Attacks against the CFS Scheme
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:04:32
5.1. Code-Based Digital Signatures
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:04:21
5.2. The Courtois-Finiasz-Sendrier (CFS) Construction
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:04:03
4.9. Goppa codes still resist
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:06:45
4.8. Attack against Algebraic Geometry codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:05:47
4.7. Attack against Reed-Muller codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Vidéo pédagogique
00:05:31
4.5. Error-Correcting Pairs
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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,

• Vidéo pédagogique
00:03:56
4.4. Attack against subcodes of GRS codes
Marquez-Corbella
Irene
Sendrier
Nicolas
Finiasz
Matthieu

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

• Conférence
01:10:11
Opponency revisited
Süsstrunk
Sabine

Opponency revisited

• Conférence
01:01:24
An Introduction to Iris: Higher-Order Concurrent Separation Logic
Birkedal
Lars

Modern programming languages such as Java, Scala, and Rust are examples of concurrent higher-order imperative programming languages.

• Conférence
01:05:05
Opinion polarization and network segregation. Modelling a complex Relationship
Flache
Andreas

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

• Conférence
01:11:17
21 Molecular Algorithms Using Reprogrammable DNA Self-Assembly
Woods
Damien

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

• Conférence
01:04:20
Topological insights in neuroscience
Hess Bellwald
Kathryn

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

• Conférence
00:32:39
Quelques algorithmes de calcul d'enveloppe convexe en 2D
Girault
Alain

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

• Conférence
00:34:52
Modélisation de la croissance des micro-organismes
Jong
Hidde 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

• Conférence
00:27:25
Les mathématiques et la physique dans les effets spéciaux et les jeux vidéo
Neyret
Fabrice

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

• Conférence
00:24:04
Caches, montrez-vous !
Durand
Marie

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

• Conférence
00:19:54
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

• Conférence
01:18:00
Self-Supervised Visual Learning and Synthesis
Efros
Alexei 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.

• Conférence
01:08:53
Theoretical Foundations for Runtime Monitoring
Aceto
Luca

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