Title

Given k = 2^q random lists of n-bit vectors, L_1, …, L_k, each list containing m vectors, we wish to find an XOR x_1 + … + x_k (with x_i in L_i) equalling to zero. This problem has numerous applications for example in coding theory and in cryptography. The problem is likely to have a solution if m > 2^{n/k}, and the classical time/space tradeoff solves it in time O(2^{n/2} poly(log(m), n, k)). However, if the list size m is much larger, specifically if m >= 2^{n / (q + 1)}, the k-tree algorithm due to Wagner finds a solution with high probability in (essentially linear) time O(2^{n/(q + 1)} poly(log(m), n, k)).

In this talk, we give a natural algorithm that specializes to the usual time/space tradeoff if m = 2^{n/k}, and to the unmodified k-tree algorithm if m = 2^{n/(q + 1)}, but is faster than its competitors for intermediate values of m. We will also show that this extended k-tree algorithm has a reasonably low failure probability. Finally, we will discuss a generalization of this algorithm to the case where the base field is not F_2, but an arbitrary finite field.