Algorithms better than meet-in-the-middle

Question

I am given n = 256 64-bit binary vectors ∈ GF(2)^64. I am also given a k and a target vector T, and I am required to choose exactly k out of the n vectors without repetition such that their sum (mod 2) is T. Such a solution is guaranteed to exist.

Obviously, a meet-in-the-middle attack would give a solution in approximately O(n^(k / 2)). However, I am wondering if the there exists faster solutions when k is really small compared to the number of dimension 64, say for k = 16. The reason I think so is that 16 vectors can only span a 16-dimensional space and so the existence of such solution is a strong information.

I have also thought of reducing the n to 64, since we can always choose 64 vectors that span GF(2)^64. However, I believe that would violate the "exactly k" part of the requirement. Or am I missing something obvious here?

Thank you for reading, any discussion would be helpful.

Answer 1

We're given n binary vectors v_i in F_2^d and a target vector T, and we want a k-subset of {v_i} that sums to T.

The natural thing to do first is to pack the vectors into a matrix, so we form M = [v1 | v2 | ... | vn]. The problem becomes finding a binary vector w with hamming weight k such that wM = T.

This can be solved using ISD (Information-Set Decoding). First find any w0 by linear algebra. Then we want to find a low weight vector in w0 + kerL(M), where kerL means left kernel. This can be done by decoding -w0 in the code kerL(M).