Canal-U

Mon compte

Résultats de recherche

Nombre de programmes trouvés : 6513
Label UNT Vidéocours

le (3m8s)

3.5. Lee and Brickell Algorithm

In this fifth session, we will study a variant of information set decoding proposed by Lee and Brickell. So, the main idea consists in relaxing the Prange algorithm to amortize the cost of the Gaussian elimination. So, instead of error patterns with all positions on the left, we will allow error patterns of the form given in the slide. So, in the left part we have w-p coordinate to 1 and on the right hand side we allow a small number p of positions to have a value 1. So, at each ...
Voir la vidéo
Label UNT Vidéocours

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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (3m57s)

4.4. Attack against subcodes of GRS codes

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 Loidreau proposed to replace Generalized Reed–Solomon codes by some random subcodes of small codimension. However, this attack has been broken by Wieschebrink in 2006 using square code considerations. The idea of the attack is very simple. The public key is a subcode of large dimension, otherwise a generic attack could be applied. And we also know the error-correcting capacity ...
Voir la vidéo

 
FMSH
 
Facebook Twitter Google+
Mon Compte