The extended k-tree algorithm

Consider the following problem: Given k = 2(q) random lists of n-bit vectors, L-1,..., L-k, each of length m, find x(1) is an element of L-1,...,x(k) is an element of L-k such that x(1) + ... + x(k) = 0, where + is the XOR operation. This problem has applications in a number of areas, including cryptanalysis, coding theory, finding shortest lattice vectors, and learning theory. The so-called k-tree algorithm, due to Wagner, solves this problem in (O) over tilde (2(q+n)/((q+1))) expected time provided the length tit of the lists is large enough, specifically if m >= 2(n/(q+1)). In many applications, however, it is necessary to work with lists of smaller length, where the above algorithm breaks down. In this paper we generalize the algorithm to work for significantly smaller values of the list length in, all the way down to the threshold value for which a solution exists with reasonable probability. Our algorithm exhibits a tradeoff between the value of in and the running time. We also provide the first rigorous bounds on the failure probability of both our algorithm and that of Wagner.