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?

• Assuming there may be more than one solution: Do you need to find a solution consisting of exactly $m$ vectors or is a different cardinality fine as well? Commented Jul 10, 2016 at 23:10
• I was thinking of a fixed m, but I'm interested if you have any insight for the case where m is not known! Commented Jul 10, 2016 at 23:19

1 Answer

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&0&0&0&1\\ 1&1&1&0&1\\ 1&0&0&1&1\\ 1&0&1&1&0 \end{array}\right) \leadsto \left(\begin{array}{cccc|c} 1&0&0&0&1\\ 0&1&1&0&0\\ 0&0&0&1&0\\ 0&0&1&1&1 \end{array}\right) \leadsto \left(\begin{array}{cccc|c} 1&0&0&0&1\\ 0&1&1&0&0\\ 0&0&1&1&1\\ 0&0&0&1&0 \end{array}\right) \leadsto \left(\begin{array}{cccc|c} 1&0&0&0&1\\ 0&1&1&0&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{array}\right) \leadsto \left(\begin{array}{cccc|c} 1&0&0&0&1\\ 0&1&0&0&1\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{array}\right)$$ The steps performed are:

1. Add (that is, XOR) the first row to all other rows.
2. Swap the third and fourth row to obtain a one on the diagonal.
3. Add the fourth to the third row.
4. 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$.

• Thanks. This is a good idea. Could you elaborate on: 1) If "Z" refers to the integers, what is this Z/2Z notation? That means 0 or 1? Do you have any resources that further explain that notation? 2) How do we know that Gaussian elimination still applies when you change addition to be XOR? Does it work for any functions? Commented Jul 11, 2016 at 3:00
• 1) $\mathbb Z/2\mathbb Z$ is the quotient ring of the integers modulo its ideal of multiples of $2$. You can read any introductory text on ring theory for more information. However, for this application, it is enough to know that $\mathbb Z/2\mathbb Z$ is the set $\{0,1\}$ with XOR and AND as addition and multiplication. 2) That Gaussian elimination works is a result of $\mathbb Z/2\mathbb Z$ being a field. It certainly does not work for an arbitrary binary function. Commented Jul 11, 2016 at 9:25