Ressource pédagogique : 3.4. Complexity Analysis

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

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.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)