# Canal-U

Mon compte
Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/3_4_complexity_analysis.32883?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Contacter le contributeur ### 3.4. Complexity Analysis

In this session, I will present the main technique to make the analysis of the various algorithms presented in this course. So, Information Set Decoding refers to a family of algorithms which is similar to the Prange algorithm that we have just seen. All variants of Information Set Decoding repeat a large number of independent iterations which all have a constant cost K and a success probability P. This means that this iteration has to be repeated an expected number of times N where N = 1/P. And the total workfactor of the algorithm will simply be N multiplied by K, the cost of the iteration. First, do we want one solution to the CSD problem or all solutions? So, we consider the CSD(H,s,w) problem. We will assume, as I said, it is the case for most cryptanalysis, that the problem we are considering has at least one solution, that is CSD(H,s,w) is not empty. There are two possibilities for the weight. Either the weight is smaller than the Gilbert-Varshamov radius, then there is exactly one solution, either the weight w is larger than the Gilbert-Varshamov radius. In that case, there are several solutions (n,w)/2^(n-k) on average. The first case is the most common and of course, there is no difference between one or all solutions because there is only one solution. In the second case, we expect that finding only one solution instead of all solutions will be less expensive. Intuitively, it is reasonable to assume that we may make the economy of a factor equal to the number of solutions. So, some probabilities. Recall that Information Set Decoding will perform many independent iterations. For one iteration, we denote P∞ the probability to find one specific solution to our problem. And we denote P1 the probability to find any one solution to our problem. If N is the number of solutions then we may write P1, as given in the slide. The exact formula will produce a value which is the minimum of 1 and N*P∞. In practice, most of the time, we will have P1 = N*P∞ when N is not too large at least. For the complexity analysis, we will have to distinguish two situations.

•
Label UNT : UNIT
•
Date de réalisation : 5 Mai 2015
Durée du programme : 6 min
Classification Dewey : Analyse numérique, Théorie de l'information, données dans les systèmes informatiques, cryptographie, Mathématiques
•
Catégorie : Vidéocours
Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche
Disciplines : Mathématiques, Informatique, Informatique, Mathématiques et informatique
Collections : 3: Message Attacks (ISD)
ficheLom : Voir la fiche LOM
•
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
•
Langue : Anglais
Mots-clés : algèbre linéaire, chiffrement à clé publique, cryptage des données, cryptographie, algorithmes
Conditions d’utilisation / Copyright : 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.

## commentaires

Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)

## Dans la même collection  