Canal-U

Mon compte
Inria

3.4. Complexity Analysis


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
Auteur(s) :
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas
FINIASZ Matthieu

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

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

FMSH
 
Facebook Twitter Google+
Mon Compte