Canal-U

3.7. May, Meurer, and Thomae Algorithm

So, with the session 7 we are entering the most advanced part of that course. The idea of what I called the  Improved Birthday Decoding is to use the so-called "representation technique" introduced by Howgrave-Graham and Joux in 2010 in which we will relax the way we construct the two lists in Birthday Decoding. So, if you remember, we could relax the size of the matrices H1 and H2 slightly to gain a polynomial factor on Birthday Decoding. But, we may push the idea further and increase the size of H1 and H2 until we reach the full size for both those matrices. If we do that, there is some redundancy in the search we will make. And in fact each solution of our problem will be represented (w,w/2) times as a sum of two error patterns of weight w/2. This means that the two sets L1 and L2 are bigger than necessary. We can try to decimate those two sets as long as we keep every solution at least one time in the intersection. So, we define the following: for any binary vector, we define Φr(x), the last r bits of the vector x and we define those two lists with an additional parameter r where we, in fact, keep in the list all the syndromes where the r final bits are set to 0. And we have the following claim that I will not prove which is that if I choose r such that 2^r is equal to the number of representation of e as a sum of two errors of half weight, then any element, any solution of our problem is represented in the intersection with probability at least one half. The Improved Birthday algorithm works as follows: first, we cut the matrix H in two parts, H'and H'', and then we will build the two lists L1 and L2. L1 is constructed by making a first recursive call to the computational syndrome decoding with the matrix H'and the weight w/2. This will cost the square root of (n, w/2) plus the number of solutions. We store the result of that first computation, then we compute in a similar way the second list L2, again by solving a computational syndrome decoding problem on the lower part and keeping the syndrome corresponding to the upper part. And finally, we merge those two lists and we keep the syndromes which match on the upper part of the matrix.