3.8. Becker, Joux, May, and Meurer Algorithm

Now in session 8, we willpresent yet another evolution of information set decoding. Before presenting thisimprovement, we will first improve the Birthday Decodingalgorithm what I call a Further Improvement of Birthday Decoding. I will consider thetwo following lists. The difference betweenthose two lists and those we had before is the + ɛ that youcan find in the weight of the errors e1 and e2. Those lists depend onanother parameter ɛ. What is the meaningof that parameter? Well, the idea is thefollowing: if you add two words of weight w/2 and length n, you expect that you obtain a sum of weight w-(w²/2n). That is, in fact, thatyou expect that those two words have w²/4nnon-zero positions in common. Now, if we shift things a little bit and if wechoose ɛ such that ɛ = (w/2+ɛ)²/n, then two words of weight (w/2) + ɛ and length n are expectedto have ɛ non-zero positions in common and a sum ofweight w which is the target weight of oursyndrome decoding problem. Note that in additionto the above property with a non-zero valueof ɛ, (w,w/2)*(n-w,ɛ) different ways to write aword of weight w, a word e, as a sum of twoerror patterns e1 and e2 of weight (w/2)+ɛ, that is, thenumber of representation will increase. All of this togetherallows us to give that claim. If we choose 2^r and ɛ as described here, then anysolution e to our problem is represented in theintersection of the two sets above with the probability 1/2. And if we do that andimplement the Birthday Decoding with those two lists, theworkfactor will simplify, if I may say, into the following formula which is true up toa polynomial factor. And, I'm not going toexplain why it is a polynomial factor now and ratherthan a constant factor. Improving BirthdayDecoding has an impact on the May, Meurer and Thomaealgorithm we have just seen. Instead of the formula wehave here, in green, that is true up to a constantfactor, by using the Further Improved Birthday Decoding,we could obtain this formula which is better for anyvalue of the parameter, which is true up to a polynomial factor. This idea and thisimprovement is the embryo of the next improvement ofinformation set decoding. This improvement is due toBecker, Joux, May and Meurer. And the idea is to let ɛ, that is the increase in theweight of the half error patterns. We let ɛ grow beyond the optimal valuethat is much beyond w²/4n. If we do that and theworkfactor of the Birthday Decoding becomes this formula with L equal to the list size and2^r is the number of representative which isgiven by the formula here. We may also write theformula in the following form introducing the value μ which is the probability thatis described on the slide.