le (3m8s)

# Résultats de recherche

**6513**

le (6m37s)

## 3.6. Stern/Dumer Algorithm

In this session, we will present the Stern algorithm for decoding. In fact, the idea is to combine two algorithms that we have seen before, the Lee and Brickell algorithm and the Birthday Decoding. So, instead of a full Gaussian elimination, we will simply have a partial Gaussian elimination as presented here. And if we look at the lower part, what is called step 1, in red here in this slide, it is, in fact, a smaller CSD problem with a smaller matrix H', with a smaller target syndrome s' and with ... Voir la vidéole (7m28s)

## 3.7. May, Meurer, and Thomae Algorithm

So, with the session 7 we are entering the most advanced part of that course. The idea of what I called the Improved Birthday Decoding is to use the so-called "representation technique" introduced by Howgrave-Graham and Joux in 2010 in which we will relax the way we construct the two lists in Birthday Decoding. So, if you remember, we could relax the size of the matrices H1 and H2 slightly to gain a polynomial factor on Birthday Decoding. But, we may push the idea further and increase the size of H1 and ... Voir la vidéole (8m33s)

## 3.8. Becker, Joux, May, and Meurer Algorithm

Now in session 8, we will present yet another evolution of information set decoding. Before presenting this improvement, we will first improve the Birthday Decoding algorithm what I call a Further Improvement of Birthday Decoding. I will consider the two following lists. The difference between those two lists and those we had before is the + ɛ that you can find in the weight of the errors e1 and e2. Those lists depend on another parameter ɛ. What is the meaning of that parameter? Well, the idea is the following: if ... Voir la vidéole (8m27s)

## 3.9. Generalized Birthday Algorithm for Decoding

The session nine is devoted to the application of the Generalized Birthday Algorithm to decoding. The Generalized Birthday Algorithm was presented by David Wagner in 2002, in a more general context. In fact, at order a, the Generalized Birthday Algorithm solves the following problem: we are given 2^a lists of vectors of size L and we want to find xi, one in every list Li, such that the sum of all the xi is 0. If the lists Li are large enough, then the algorithm runs in time 2^(l/(a+1)). Note that the ... Voir la vidéole (8m37s)

## 3.10. Decoding One Out of Many

The final session of this week is devoted to Decoding One Out of Many. Decoding One Out of Many is interested in solving the following variant of Syndrome Decoding. In this variant, the only difference with the usual Syndrome Decoding is that we are interested in a set of syndromes rather than a single syndrome. So, the instance will be S, a set of syndromes of size N. H, a parity-check matrix and w an integer, the weight we are looking for. And we are interested in an error e, such that ... Voir la vidéole (4m47s)

## 4.1. Introduction

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 of decoding a random linear code; these attacks has already been studied in the third week, by Nicolas Sendrier. Notice that efficient generic attack just makes the use of larger code in the McEliece scheme necessary. And we also have Key Attacks. These attacks try to retrieve the code structure, rather than attempting to use an specific decoding algorithm. These attacks ... Voir la vidéole (6m21s)

## 4.2. Support Splitting Algorithm

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 if they are equal up to a fixed linear map. Each linear map is the composition of a permutation, a scalar multiplication, which could vary for each coordinate, and a field automorphism. But for this session, we consider a more restrictive definition, which coincides with the general case for binary linear code. Two codes are permutation-equivalent if they are ... Voir la vidéole (5m19s)

## 4.3. Distinguisher for GRS codes

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-Solomon codes. Let us recall the definition of Generalized Reed-Solomon codes. We will need an n-tuple of mutually distinct elements of Fq. We need a vector b which is an n-tuple of nonzero elements of Fq. We need to define the vector space of all polynomials of degree at most k and we also need to define a evaluation map. Then the ... Voir la vidéole (3m57s)