XOR - Is it possible to get a, b, c from a⊕b, b⊕c, a⊕c?

Question

Just got a simple question from a friend; still thinking. Let's share it!

Is it possible to get a, b, c when you have a⊕b, b⊕c, a⊕c ?

where ⊕ is the boolean XOR (exclusive OR) operator.
a,b,c are any boolean numbers with the same length.
For the sake of simplicity, consider a,b,c as bytes (length is 8 bits).

Edit: You can use other operators too.
Edit 2: Though it's preferable to use only ⊕ (if possible) (removed, use any operator)

---

Note 1: Answer without explanations (e.g. yes/no) are not allowed.
Note 2: This is a puzzling programming, math-related question and could be placed on Puzzling.SE, Programming.SE, StackOverflow and Math.SE. So excuse me or migrate the question if I pasted it on the wrong SE forum.

Answer 1

If you're given just a⊕b and b⊕c, then you can calculate

  (a⊕b) ⊕ (b⊕c)
= a ⊕ (b ⊕ b) ⊕ c   (since ⊕ is associative)
= a ⊕ 0 ⊕ c         (since X⊕X=0 for any X)
= a ⊕ c              (since X⊕0=X for any X)

so in effect when you're given a⊕b, b⊕c, a⊕c you've only been given two numbers (because the last one is redundant). So (assuming a,b,c are 8 bits as in the question) you only have 16 bits of information, and hence you can't work out all of a,b and c since that would require 24 bits of information.

Answer 2

This is not possible.

Consider the two cases where a, b and c are all true or all false. Now in both cases we have

a⊕b = b⊕c = a⊕c = false

And more generally, $(¬a)⊕(¬b)=a⊕b$, so if $a,b,c$ is a solution, then so is $¬a,¬b,¬c$. (from Klaus Draeger)

Answer 3

Your question with the XOR operator mathematically reduces to:

In the $\mathbb{F}_{2^m}$ field (field of characteristic 2 whose elements can be represented as sequences of $m$ bits, and where addition is bitwise XOR), is the following matrix: $$ M = \left( \array{1\ 1\ 0\\1\ 0\ 1\\0\ 1\ 1}\right) $$ invertible ? Indeed, for a dimension-3 vector $V = (x, y, z)$, multiplying $V$ by the matrix above yields a vector $M·V = (x⊕y, x⊕z, y⊕z)$. For the operation to be reversible, the matrix $M$ must be invertible.

But that matrix is not invertible, because the third line is equal to the XOR of the two first lines. The conclusion is thus that it is not possible, in all generality, to recover $a$, $b$ et $c$ from $a⊕b$, $a⊕c$ and $b⊕c$.

We can add that the matrix, being non-invertible, has a non-trivial kernel: there is a subspace $K$ of $(\mathbb{F}_{2^m})^3$ that contains all vectors V such that $M·V = (0, 0, 0)$. The rank of $M$ is 2, meaning that the subspace $K$ has dimension 1; it is not hard to see that $K$ consists in exactly the vectors $(x, x, x)$ for all possible values of $x$. When you have a solution $S = (a, b, c)$ for your equation (the values $a$, $b$ and $c$ match the known values of $a⊕b$, $a⊕c$ and $b⊕c$), then the set of solutions is exactly $\left\{ S+V | V \in K \right\}$. In other words, when you have a solution, you have exactly $2^m$ solutions, and nothing to distinguish between them.

We can thus conclude that it is never possible to unambiguously reconstruct $a$, $b$ and $c$ from $a⊕b$, $a⊕c$ and $b⊕c$.

---

The same result extends to more than three values: you cannot unambiguously recover the $n$ values $a_0, a_1,… a_{n-1}$ from the set of $n$ values $a_i⊕a_{i+1}$ for all $i$ from $0$ to $n-1$ (taking $a_n = a_0$).

Answer 4

No, since,

A ⊕ B = B ⊕ C = A ⊕ C = 0

can be either

• A = B = C = 0 or
• A = B = C = 1

Answer 5

_{(as an extension of GOTO 0's answer)}
This is also not possible if you consider these as binary numbers, you cannot determine the values of a, b, or c. For instance:

a = 0b11001111010
b = 0b11001111101
c = 0b11001111001

All three of the xors for these binary representations compress the results down to at most three bits (the right-most three). Anywhere that all three numbers match bits will end up as 0, resulting in an inconclusive initial state since the matching bits are effectively "lost".

a⊕b = 0b111
b⊕c = 0b100
a⊕c = 0b011

Answer 6

There are only a few cases, let's perform a quick inspection:

Let $$a⊕b=k_1$$ $$b⊕c=k_2$$ $$c⊕a=k_3$$ , we have

\begin{matrix} a & b & c & &k_1 & k_2 & k_3\\ -&-&-&-&-&-&-&\\ 0 & 0 & 0 & \rightarrow &0 & 0 & 0\\ 0 & 0 & 1 & \rightarrow &0 & 1 & 1\\ 0 & 1 & 0 & \rightarrow &1 & 1 & 0\\ 0 & 1 & 1 & \rightarrow &1 & 0 & 1\\ 1 & 0 & 0 & \rightarrow &1 & 0 & 1\\ 1 & 0 & 1 & \rightarrow &1 & 1 & 0\\ 1 & 1 & 0 & \rightarrow &0 & 1 & 1\\ 1 & 1 & 1 & \rightarrow &0 & 0 & 0 \end{matrix}

Hence only $$(k_1, k_2, k_3) \in \{(000), (011), (110), (101)\}$$ are solvable.

In addition, please note that:

1. The RHS of the table is symmetric.
2. All possible combination of $(k_1, k_2, k_3)$ have even number of '1's since summing the three equations: $$a⊕b=k_1$$ $$b⊕c=k_2$$ $$c⊕a=k_3$$ yields $$ k_1⊕k_2⊕k_3 =a⊕a⊕b⊕b⊕c⊕c=0$$

Answer 7

We can't get the precise values of $a$, $b$ and $c$, but we can determine them up to a constant.

More specifically, given any solution $(a, b, c)$ and any constant $C$, then $(a \oplus C, b \oplus C, c \oplus C)$ is also a solution, because the $C$'s cancel out when we XOR them. Furthermore, we can show that all solutions to the given system of equations can, in fact, be derived from a single solution in this way.

---

To show this, it's useful to generalize a bit. First of all, we note that the problem with three equations is simply a special case of the same problem with $n$ equations, where we're given $$\begin{aligned} a_2 \oplus a_1 &= b_1 \\ a_3 \oplus a_2 &= b_2 \\ &\ \ \vdots \\ a_n \oplus a_{n-1} &= b_{n-1} \\ a_1 \oplus a_n &= b_n \end{aligned}$$ with known $(b_1, \dotsc, b_n)$, and wish to solve for $(a_1, \dotsc, a_n)$.

Next, it's useful to note that bitwise XOR is equivalent to (vector) subtraction modulo 2 (and also, of course, to vector addition modulo 2, since those are the same thing; but the equivalence to subtraction gives a nicer generalization here). That is, we may generalize the problem to $$\begin{aligned} a_2 - a_1 &= b_1 \\ a_3 - a_2 &= b_2 \\ &\ \ \vdots \\ a_n - a_{n-1} &= b_{n-1} \\ a_1 - a_n &= b_n \end{aligned}$$ where the $a$'s and $b$'s are elements of an algebraic group* and $-$ is the subtraction operation defined by $x - y = x + (-y)$ (where $+$ is the group operation, and $-y$ is the inverse element of $y$). You can easily check that bitstrings indeed satisfy the definition of a group, with XOR as the group operation and each bitstring as its own inverse.

Why is this useful? Well, because as long as we're just doing addition (and subtraction, which is just addition of an inverse element), we can treat any such group elements just as if they were ordinary numbers, because (by definition) they obey the same algebraic rules. In particular, by adding $a_i$ to both sides of the $i$-th equation and simplifying, we can rearrange the equations above into the following equivalent form: $$\begin{aligned} a_2 &= b_1 + a_1 \\ a_3 &= b_2 + a_2 \\ &\ \ \vdots \\ a_n &= b_{n-1} + a_{n-1} \\ a_1 &= b_n + a_n. \end{aligned}$$

From this, we can see that, if we just pick some value for $a_1$, then we can immediately read out the values of $a_2, \dotsc, a_n$ from the first $n-1$ equations, like this: $$\begin{aligned} a_2 &= b_1 + a_1 \\ a_3 &= b_2 + b_1 + a_1 \\ &\ \ \vdots \\ a_{n-1} &= b_{n-2} + \dotsb + b_2 + b_1 + a_1 \\ a_n &= b_{n-1} + b_{n-2} + \dotsb + b_2 + b_1 + a_1 \end{aligned}$$

Thus, for each value of $a_1$, there can be (at most) one solution to these equations.

Whether or not the values of so obtained in fact are a solution then depends on the last equation, which needs to yield the original $a_1$ value. However, it turns out that this doesn't depend on which value we pick! In particular, substituting the value of $a_n$ calculated above into the last equation gives $$a_1 = b_n + b_{n-1} + b_{n-2} + \dotsb + b_2 + b_1 + a_1.$$

But now we can simply subtract $a_1$ from both sides to reduce this equation to: $$0 = b_n + b_{n-1} + b_{n-2} + \dotsb + b_2 + b_1.$$

So if this equation, which only contains the $b$ values, holds, then so will the previous one (for any $a_1$!), and so every choice of $a_1$ will yield a solution to the original equation. In fact, all these solutions will be of the form $a_i = a_i^0 + a_1$, where $a_i^0$ is the value of $a_i$ obtained by starting with $a_1 = 0$. And conversely, if the last equation above does not hold, then the original system of equations is inconsistent, and has no solution at all.

^{*) In fact, I didn't even need to assume that the group is abelian, i.e. that $x + y = y + x$, although for XOR this does certainly hold. In a non-abelian group you may not be able to freely reorder the terms in a sum, which can sometimes get awkward, but I didn't really have much need for that here, so I decided to go ahead and prove a slightly more general result without that assumption.}

---

Ps. If you still remember indefinite integrals from high school math, you may recall that the solution $F$ to an integral equation like $F = \int f(x)\,dx$ is only defined up to a constant: if $F$ is a solution, then so is $F + C$ for any constant $C$. This is the exact same situation, just with discrete pairwise differences instead of differentials (and with XOR instead of ordinary subtraction).

Basically, if we're only given the differences between adjacent elements in a sequence, we cannot uniquely determine the original sequence without some way to fix the starting value. Having the sequence loop around in a circle doesn't change this; it just adds an extra constraint that all the differences must add up to zero for there to be any solution at all.

Answer 8

@psmears @GOTO 0 and @Ian MacDonald have already asked the basic question. This is another extension.

This question is interesting because operators lose information. The question fundamentally asks what is lost and what can be recovered.

It reminds me of a geometry trick:

Take any 4 points $A,B,C,D$ on a plane. Compute the middle points $E,F,G,H$, one between each in turn (the fourth middle point $H$ is between $D$ and $A$). Whatever the configuration of $ABCD$, $EFGH$ is always a parallelogram.

Computing the middle point is similar to addition here. The fact that $EFGH$ has a property that $ABCD$ did not have is typically a loss of information.

Back to XOR, note that with $a$, $a⊕b$ and $a⊕c$ you can recover everything.

There exist some applications using XOR with similar properties, see https://en.wikipedia.org/wiki/Fountain_code. The explanation there is a little general, but basically XOR combinations of a set of numbers (a, b and c, and more) are numerous and have the interesting property that if you receive only part of these combinations you can recover everything. This is useful for multicasting a signal to receivers on an unreliable medium.

From Fountain code - Wikipedia:

IETF RFC 5053 specifies in detail a systematic Raptor code, which has been adopted into multiple standards beyond the IETF, such as within the 3GPP MBMS standard for broadcast file delivery and streaming services, the DVB-H IPDC standard for delivering IP services over DVB networks, and DVB-IPTV for delivering commercial TV services over an IP network.

Answer 9

Remember that $\oplus$ is addition mod 2. So we wish to solve the system of equations

$$\begin{equation*} \begin{alignedat}{4} x & = & a & {}+{} & b & & \\ y & = & & & b & {}+{} & c \\ z & = & a & & & {}+{} & c \end{alignedat} \end{equation*}$$

Solving this over the real numbers we get the solution

$$\begin{equation*} \begin{alignedat}{4} a & = & \frac{x}{2} & {}-{} & \frac{y}{2} & {}+{} & \frac{z}{2} \\ b & = & \frac{x}{2} & {}+{} & \frac{y}{2} & {}-{} & \frac{z}{2} \\ c & = & -\frac{x}{2} & {}+{} & \frac{y}{2} & {}+{} & \frac{z}{2} \end{alignedat} \end{equation*}$$

We know by the theory of linear algebra that this solution is unique. However, this solution does not work in $\mathbb{Z}_2$, because we cannot divide by 2 in that field. Hence the system is not invertible.

Answer 10

No.

XOR is true if exactly one of the inputs is true. Which means, if you negate both inputs, XOR stays the same. This means you can't distinguish "a⊕b" from "(not a)⊕(not b)".

Say you have an algorithm to calculate a,b,c for given a⊕b, a⊕c and b⊕c. You use it and get a', b', c'. If someone else comes and says "no, the correct solution is actually (not a', not b', not c')", nobody can decide which is correct.

It doesn't matter if a,b,c are single-bit booleans or longer. The argument applies to each bit.

Answer 11

a⊕b ⊕ b⊕c == a⊕c So, as already noted, you have 2 equations with 3 unknowns, and this is not possible, in general.

However, this is a common scenario in cryptography. If b is the ciphertext, and a and c are two plaintexts, you can use a⊕b and b⊕c to get the XOR of two plaintexts, a⊕c. You can then use linguistic analysis, statistical methods, etc., to decipher a, c, and then b. But this relies on additional information about a and c.

Answer 12

I know there have been enough good answers already, but here is what I personally find to be the simplest:

No. We can easily list all possible ways to xor these three numbers:

a⊕b ⊕ a⊕c = b⊕c
a⊕b ⊕ b⊕c = a⊕c
a⊕c ⊕ b⊕c = a⊕b
x⊕x = 0 for any x
0⊕x = x for any x

This means that any expression involving these numbers and 0 combined with xor will always reduce to one of those numbers again (your three numbers and 0 are closed under xor). As a consequence, nothing else can be the value of any such expression, a, b and c are no exception.