The Extended k-tree Algorithm

摘要

Consider the following problem: Given k = 2~q random lists of n-bit vectors, L_l…..L_k, each of length m, find x_l ∈ L_l,…, x_k ∈ L_k, such that x_l +…++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(2~(q+~n/(q+1)) expected time provided the length m 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 m, 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 m and the running time. We also provide the first rigorous bounds on the failure probability of both our algorithm and that of Wagner. As a third contribution, we give an extension of this algorithm to the case where the vectors are not binary, but defined over an arbitrary finite field F_r, and a solution to λ_lx_l + … + λ_kx_k = 0 with λ_I∈ F_r* and x_I ∈ L_I is sought.