55
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can we use operators that aren't ⊕? $\endgroup$ – Ian MacDonald Sep 2 '15 at 13:51
  • 2
    $\begingroup$ Are a, b, c integers or booleans? $\endgroup$ – Ian MacDonald Sep 2 '15 at 13:55
  • 2
    $\begingroup$ One could also notice that if x=a⊕b, y=b⊕c, z=a⊕c, then z=x⊕y. Thus, in terms of information, the three values x, y, z contain only 2 bits of information and thus cannot determine 3 independent values. In terms of algebra, we could say that the set of three equations are linearly dependent and define a plane in the Boolean space Oabc instead of a point. $\endgroup$ – ach Sep 2 '15 at 17:50
  • 1
    $\begingroup$ @AndreyChernyakhovskiy in terms of my answer, this shows that the 3x3 system is not full-rank (mod 2). $\endgroup$ – asmeurer Sep 2 '15 at 20:29
  • 2
    $\begingroup$ @Spook: There's nothing in the definition of an operator that means it must cause data loss... for example, you could define an operator ⊞ on numbers considered as bit strings, where abc⊞def=abcdef (ie concatenation) - clearly this doesn't lose information; furthermore, if you're given a+b, b+c, c+a (i.e. normal addition) then you can recover a,b & c. Since XOR is equivalent to addition (mod 2), it's not unreasonable to assume the same would be true there - it just happens, as the answers show, to be false :) $\endgroup$ – psmears Sep 9 '15 at 6:59

12 Answers 12

108
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ @Jet: It's impossible because any valid solution can have any specific bit inverted in all three to become another valid solution. $\endgroup$ – Deusovi Sep 2 '15 at 15:53
  • 5
    $\begingroup$ @Jet: It's a very similar concept, yes. Basically there are 2^24=16777216 possibilities for what a,b,c can be, but only 2^16=65536 possibilities for what you'll get from a⊕b, b⊕c, a⊕c (since any one of those values is uniquely determined by the other two). So there must be combinations of a⊕b, b⊕c, a⊕c for which there are multiple solutions for a,b,c - and in fact there are exactly 256 for each. $\endgroup$ – psmears Sep 2 '15 at 20:01
  • 2
    $\begingroup$ @BolucPapuccuoglu: Whatever X you take, (X⊕0) is equal to X - because 0⊕0=0 and 1⊕0=1 - i.e. 0 is the identity for XOR. $\endgroup$ – psmears Sep 3 '15 at 9:35
  • 4
    $\begingroup$ +1 for working out how much information you're given. I quickly ran into a⊕b ⊕ b⊕c just giving me a⊕c which I already had, but didn't clue in to the fact that this meant there wasn't enough information to give a unique solution. $\endgroup$ – Peter Cordes Sep 3 '15 at 19:42
  • 4
    $\begingroup$ @miracle173: Of course you need associativity, that's why I mentioned it right there by the calculation :) I don't think it's really necessary to prove the well-known result that exclusive-or is associative here, just as most people don't prove the associativity of addition every time they use it; anyone needing that proof would be better served by another question. $\endgroup$ – psmears Sep 7 '15 at 7:20
68
$\begingroup$

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)

$\endgroup$
  • 5
    $\begingroup$ Something something DeMorgan something... it's been a long time! $\endgroup$ – corsiKa Sep 2 '15 at 16:54
  • 4
    $\begingroup$ For mathy types: this function is not injective, so it is not invertible. $\endgroup$ – imallett Sep 2 '15 at 22:45
  • 8
    $\begingroup$ @KlausDraeger: Assuming 8 bits, ¬a is just a ⊕ 255. This points at the even more general observation that (a⊕x), (b⊕x), (c⊕x) is also a solution, for any x. $\endgroup$ – MSalters Sep 3 '15 at 9:34
22
$\begingroup$

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$).

$\endgroup$
  • 1
    $\begingroup$ Would the same be true of any additive group of integers congruent modulo an even number, but not for groups of integers congruent modulo odd numbers? $\endgroup$ – supercat Sep 3 '15 at 15:32
  • $\begingroup$ It is so frightening to see that you wrote the only answer explcitely mentioning linear algebra that I decided to register and upvote! $\endgroup$ – Michael Le Barbier Grünewald Sep 4 '15 at 15:06
  • 3
    $\begingroup$ -1 to much math for such a simple question. $\endgroup$ – miracle173 Sep 7 '15 at 5:57
  • $\begingroup$ @miracle Proofs by contradiction are usually horribly boring and non-constructive, this question being a nice example of that. Not sure why you have such a strong antipathy against simple math. $\endgroup$ – Voo Sep 8 '15 at 17:17
18
$\begingroup$

No, since,

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

can be either

  • A = B = C = 0 or
  • A = B = C = 1
$\endgroup$
  • 3
    $\begingroup$ +1 The other answers explain many interesting related concepts, but as an answer to a puzzle, this is as simple as it gets. $\endgroup$ – JiK Sep 3 '15 at 13:46
13
$\begingroup$

(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
$\endgroup$
9
$\begingroup$

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$$
$\endgroup$
  • 1
    $\begingroup$ Note that the second 4 are the same as the first four. That's why there are only 4 solvable cases. But even if there are 4 solvable cases, none of them has only one solution, each of them has two solutions, a,b,c and ¬a,¬b,¬c. So we can't define exact a,b,c if we are given k1,k2,k3 in these four cases, and we can say it's impossible to get a,b,c in other four cases. So anyway, it's not possible to exactly find one a,b,c in all cases. $\endgroup$ – Jet Sep 3 '15 at 6:55
  • 1
    $\begingroup$ In my opinion, this is the clearest answer. $\endgroup$ – Guntram Blohm Sep 4 '15 at 9:20
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the case of integration it somehow seems less useless that f(0) could be any value and there is a corresponding solution, than it seems in this case that a could be any value and there is a corresponding solution :-) $\endgroup$ – Steve Jessop Sep 4 '15 at 1:14
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ So because you can't calculate a solution with the method you have tried, there is no solution? That is a strange argumentation. Maybe you use the wrong method! $\endgroup$ – miracle173 Sep 7 '15 at 5:42
  • 1
    $\begingroup$ There's a reason I pointed out that the solution unique. $\endgroup$ – asmeurer Sep 7 '15 at 8:28
5
$\begingroup$

@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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.