Paper Info
Title
The Extended k-tree Algorithm
Abstract
Consider the following problem: Given k=2q random lists of n-bit vectors, L 1,…,L k , each of length m, find x 1∈L 1,…,x k ∈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 $\tilde{O}(2^{q+n/(q+1)})$ expected time provided the length m of the lists is large enough, specifically if m≥2n/(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 $\mathbb{F}_{r}$, and a solution to λ 1 x 1+⋅⋅⋅+λ k x k =0 with $\lambda_{i} \in \mathbb{F}_{r}^{*}$ and x i ∈L i is sought.
Year
DOI
Venue
2012
10.1007/s00145-011-9097-y
Symposium on Discrete Algorithms
Keywords
Field
DocType
following problem,failure probability,expected time,extended k-tree,l i,smaller length,list length m,coding theory,so-called k-tree algorithm,l k,length m,birthday problem,correlation attack
Discrete mathematics,Combinatorics,Finite field,Birthday problem,Bitwise operation,Lattice (order),K-tree,Algorithm,Coding theory,Mathematics,Binary number,Lambda
Journal
Volume
Issue
ISSN
25
2
0933-2790
ISBN
Citations 
PageRank 
978-0-89871-698-6
18
0.94
References 
Authors
13
2
Name
Order
Citations
PageRank
Lorenz Minder1925.53
Alistair Sinclair21506308.40