Given a set of vectors S, finding a subset s that XORs to x is trivial: Use Gaussian elimination under GF(2). Moreover, any such subset can be found by adding arbitrary members of the matrix's nullspace.
However, I'm looking to solve cases where the cardinality of s has certain properties, such as:
- |s| = k
- |s| mod j = k
- |s| is optimized, that is, the smallest of all possible solutions.
I have not been able to find any way to solve these using linear algebra. I believe the reason is that the properties I describe above are not expressible in GF(2). The only solution paths I've been able to identify devolve essentially into some type of NP-like search, reminiscent of the set-cover problem.
Is there a means to solve this using linear algebra?
Is there a means to solve this using a more efficient approach than set-cover like search?
Are there any ways to capture characteristics of s, such as its cardinality, in GF(2)?
This is a high computational complexity problem if you want a small number of vectors adding to a given target, with essentially no better than brute force solutions known.
Given small $k,$ for simplicity assume it is even, you can form all $ k/2$ vector sums from the set (at complexity $O(|S|^{k/2})$) sort them and look for a pair of sums in the set that XOR to $x.$
Related CS Stackexchange Question:
https://cstheory.stackexchange.com/questions/10396/0-1-vector-xor-problem
Related Crypto Stackexchange Question:
https://crypto.stackexchange.com/questions/71787/collision-resistance-of-partial-sha-256-hashes-xored/71861#71861
For $k$ a power of 2 there is a known algorithm with some improvement of the complexity.
http://people.eecs.berkeley.edu/~daw/papers/genbday.html