A Non Asymptotic Analysis of Information Set Decoding.
Yann Hamdaoui, Nicolas Sendrier · 2013
Abstract. We propose here a non asymptotic complexity analysis of some variants of information set decoding. In particular, we give this analysis for the two recent variants – published by May, Meurer and Thomae in 2011 and by Becker, Joux, May and Meurer in 2012 – for which only an asymptotic analysis was available. The purpose is to provide a simple and accurate estimate of the complexity to facilitate the paramater selection for code-based cryptosystems. We implemented those estimates and give a comparison at the end of the paper. Notation: – Sn(0, w) is the radius w sphere centered in 0 in the Hamming space {0, 1} n. – |X | denotes the cardinality of the set X. 1