Vidéo pédagogique

3.4. Complexity Analysis

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

In this session, I willpresent the main technique to make the analysis of thevarious algorithms presented in this course. So, Information SetDecoding refers to a family of algorithms which issimilar to the Prange algorithm that we have just seen. All variants of InformationSet Decoding repeat a large number of independentiterations which all have a constant cost K and a success probability P. This means that thisiteration has to be repeated an expected number oftimes N where N = 1/P. And the totalworkfactor of the algorithm will simply be N multipliedby K, the cost of the iteration. First, do we want one solution to the CSD problem or all solutions? So, we consider theCSD(H,s,w) problem. We will assume, as Isaid, it is the case for most cryptanalysis, thatthe 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 issmaller than the Gilbert-Varshamov radius, then there isexactly one solution, either the weight wis larger than the Gilbert-Varshamov radius. In that case, there areseveral solutions (n,w)/2^(n-k) on average. The first caseis the most common and of course, there is nodifference between one or all solutions becausethere is only one solution. In the second case, weexpect that finding only one solution instead of allsolutions will be less expensive. Intuitively, it isreasonable to assume that we may make the economy of afactor equal to the number of solutions. So, some probabilities. Recall that Information SetDecoding will perform many independent iterations. Forone iteration, we denote P∞ the probability to find onespecific solution to our problem. And we denote P1 theprobability to find any one solution to our problem. If N is the number ofsolutions then we may write P1, as given in the slide. The exact formulawill produce a value which is the minimum of 1 and N*P∞. In practice, most of thetime, we will have P1 = N*P∞ when N is not too large at least. For the complexity analysis, we willhave to distinguish two situations.

Langue :
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). 3.4. Complexity Analysis. [Vidéo]. Canal-U. (Consultée le 27 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème