Decomposing a vector of random bits into constituent XORed vectores Suppose I have N potential predefined, publicly known (pseudo?) random bit vectors:


sequence 1: 1001000101010111001...
sequence 2: 0100101011101010100...
...
sequence n: 0101101010111010001...


Suppose you randomly choose a few (call it m) sequences and XOR them bitwise into a final vector. If one wanted to find out which vectors made up the final vector, the only solution that comes to my mind is to enumerate the n-choose-m combinations and start ruling out sets of m.

Is there a way to be smarter about this?  Is there a way to start ruling out individual vectors instead of just the combinations of m?

Also, does the practice of XORing many pseudorandom vectors have a name?
If solutions of more or fewer than $m$ vectors are also admissible, this is easy: XOR of $n$-bit strings can be rephrased as addition in the vector space $(\mathbb Z/2\mathbb Z)^n$. You are looking for a solution to the linear equation
$$ a_1v_1+\dots+a_mv_m=y $$
where $v_1,\dots,v_m\in (\mathbb Z/2\mathbb Z)^n$ are all the public bit vectors, $y\in(\mathbb Z/2\mathbb Z)^n$ is the sum of a subset,
and the coefficients $a_1,\dots, a_m$ must be $0$ or $1$, that is, in $\mathbb Z/2\mathbb Z$.

As over any field, Gaussian elimination can be used to find a solution to such a system.

Here's an example: Suppose given the $4$-bit vectors $1111$, $0100$, $0101$, $0011$ and the result $1110$ of XORing some of them. We write those vectors into the columns of a matrix and perform the elimination (which becomes quite simple in this case as there is only one non-zero field element):
$$
\left(\begin{array}{cccc|c}
  1&amp;0&amp;0&amp;0&amp;1\\
  1&amp;1&amp;1&amp;0&amp;1\\
  1&amp;0&amp;0&amp;1&amp;1\\
  1&amp;0&amp;1&amp;1&amp;0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&amp;0&amp;0&amp;0&amp;1\\
  0&amp;1&amp;1&amp;0&amp;0\\
  0&amp;0&amp;0&amp;1&amp;0\\
  0&amp;0&amp;1&amp;1&amp;1
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&amp;0&amp;0&amp;0&amp;1\\
  0&amp;1&amp;1&amp;0&amp;0\\
  0&amp;0&amp;1&amp;1&amp;1\\
  0&amp;0&amp;0&amp;1&amp;0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&amp;0&amp;0&amp;0&amp;1\\
  0&amp;1&amp;1&amp;0&amp;0\\
  0&amp;0&amp;1&amp;0&amp;1\\
  0&amp;0&amp;0&amp;1&amp;0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&amp;0&amp;0&amp;0&amp;1\\
  0&amp;1&amp;0&amp;0&amp;1\\
  0&amp;0&amp;1&amp;0&amp;1\\
  0&amp;0&amp;0&amp;1&amp;0
\end{array}\right)
$$
The steps performed are:


Add (that is, XOR) the first row to all other rows.
Swap the third and fourth row to obtain a one on the diagonal.
Add the fourth to the third row.
Add the third to the second row.


Now we can read off the result in the rightmost column: The target vector is the XOR of the first three input vectors, that is, $1111\oplus0100\oplus0101$.