0
$\begingroup$

I'm working on a somewhat-unique linear algebra problem arising from XORing files together in order to encode them, and then figuring out how to subsequently recreate the original files from the encoded ones. For a trivial ($n=3$) example, files $f1-f3$ are combined to create the encoded files $c1-c3$ according to the following system:

$c1 = f1 \\ c2 = f1 \oplus f2 \oplus f3 \\ c3 = f1 \oplus f3$

It then follows that given the encoded files $c1-c3$, we can recreate files $f1-f3$ as follows:

$f1 = c1\\ f2 = c2 \oplus c3 \\ f3 = c1 \oplus c3$

So, given the above examples (which I just wrote/solved ad-hoc by looking at it), I'm trying to figure out how to go about solve a larger system (i.e. $n \geq 100$), mathematically and eventually programatically. Looking at the above example, I see how I could maybe represent it as matrix multiplication:

$ \begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} \begin{bmatrix}f1 \\ f2 \\ f3\end{bmatrix} = \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix} $

except I'm not quite sure how to go about the math or if I'm allowed to just set up the matrices like this since I'm using $\oplus$ (which cancels itself out) instead of $+$. I'm also unsure how to go about solving the system, since I haven't done any linear algebra in almost a decade. For example, to find $f2$ in terms of $c1-c3$, should I just solve something like the matrix below?

$ \begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} \begin{bmatrix}0 \\ f2 \\ 0\end{bmatrix} = \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix} $

Anyways, any tips or pointers, even just on math terminology, operations, or help in describing what I'm trying to do, would be much appreciated. Thanks!!!

$\endgroup$
3
$\begingroup$

What you're trying to do is solve a linear equation system with values in the finite field $\mathbb{F}_2$ instead of in $\mathbb{R}$. I have great news for you: it'll work just fine! Solve it like you would solve a real-valued system, using addition of rows and such, just make sure to use $\oplus$ when you would use $+$ or $-$.

Note: Solve $$\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} \begin{bmatrix}f1 \\ f2 \\ f3\end{bmatrix} = \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix}$$ as usual, using Gaussian elimination on $$\left[\begin{array}{ccc|c}1 & 0 & 0 & c1\\ 1 & 1 & 1 & c2 \\ 1 & 0 & 1 & c3\end{array}\right].$$

If you want to find a general scheme to calculate $f1, f2, f3$ from $c1, c2, c3$, why not simply invert your coefficient matrix?

$$\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}^{-1} \begin{bmatrix}c1 \\ c2 \\ c3\end{bmatrix} = \begin{bmatrix}f1 \\ f2 \\ f3\end{bmatrix}$$

Inverting $\mathbb{F}_2$-matrices works just like with real-valued matrices, but again, use $\oplus$ when you would use $+$ or $-$. In this case, you'll get

$$\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}^{-1} = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}.$$

$\endgroup$
  • $\begingroup$ Clear, concise, the explanation and approach I was looking for. Thank you!!! :-) $\endgroup$ – Spencer Apr 26 '16 at 19:20
0
$\begingroup$

Why not take

$$ c1 = f1\\ c2 = f1 \oplus f2 \\ c3 = f1 \oplus f2 \oplus f3 $$

That way,

$$ f_2= c_2 \oplus c_1$ \\ f_3 = c_3 \oplus c_2 \oplus c_1 \\ \ldots \\ fn = c_n \oplus c_{n -1} \oplus \ldots \oplus c_1 $$

$\endgroup$
  • $\begingroup$ Clever idea! Problem is that I'm trying to distribute the coding scheme at least somewhat evenly across the space, so that a randomly-selected file $fi$ requires approximately $x$ encoded files to decrypt it, and (correspondingly) a random encoded file $ci$ is the combination of approximately $y$ files. I'm also trying to make the coding scheme unpredictable, so that it could be randomly-generated given an input of N files. $\endgroup$ – Spencer Apr 26 '16 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.