The extended k-tree algorithm

ABSTRACT

Consider the following problem: Given k = 2^q random lists of n-bit vectors, L₁, ..., L_k, each of length m, find x₁ ∈ L₁, ..., x_k ∈ L_k such that x₁ + ... + 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 Õ(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.

REFERENCES

• 1: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 2: Mihir Bellare and Daniele Micciancio. A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost. Proceedings of EUROCRYPT '97, LNCS 1233, pages 163--192, Springer-Verlag, 1997.
• 3: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM), v.50 n.4, p.506-519, July 2003 [doi>10.1145/792538.792543]
• 4: Paul Camion and Jacques Patarin. The Knapsack Hash Function proposed at Crypto'89 can be broken Proceedings of EUROCRYPT '91, LNCS 547, pages 39--53, Springer-Verlag, 1991.
• 5: Philippe Chose , Antoine Joux , Michel Mitton, Fast Correlation Attacks: An Algorithmic Point of View, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.209-221, May 02, 2002
• 6: Jean-Sebastien Coron and Antoine Joux. Cryptanalysis of a Provably Secure Cryptographic Hash Function. Cryptology ePrint Archive Report 2004/013, 2004. http://eprint.iacr.org/2004/013
• 7: Ravi Kumar , D. Sivakumar, On polynomial approximation to the shortest lattice vector length, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 07-09, 2001, Washington, D.C., United States
• 8: Vadim Lyubashevsky. On random high density subset sums APPROX-RANDOM, LNCS 3624, pages 378--389, Springer-Verlag, 2005.
• 9: Andrew Shallue. An improved multi-set algorithm for the dense subset sum problem ANTS VIII, Algorithmic Number Theory Symposium, LNCS 5011, pages 416--429, Springer-Verlag, 2008.
• 10: David Wagner, A Generalized Birthday Problem, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.288-303, August 18-22, 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms