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.