XOR

Table of contents

What it is

“Exclusive Or”, or XOR for short is a logical operator that can be found in a lot of cryptographic constructions.

This is due to XOR’s invertibility (the inverse of XOR is XOR itself) and its perfect balance of potential output values given their input values.

When used in a mathematical context, XOR is usually represented as the symbol $\oplus$. In programming languages you’ll often see the symbol ^ being used for bitwise XOR.

Truth table

To get a better understanding of the benefits the aforementioned properties provide we should start by looking at XOR’s truth table.

The first two columns of the table show that we’re dealing with two variables $a$ and $b$. The last column displays the result of computing $a \oplus b$.

Each row shows one distinct combination of potential values $a$ and $b$ can assume. Given that we’re dealing with binary data, those values are either $0$ or $1$.

In total we have $2^2 = 4$ rows that show all valid combinations (2 variables, each of which can assume 2 different values).

Translating the meaning of XOR into plain English, we can see that it means ”either this, or that is true, but not both at the same time”.

Properties

Invertibility

The first useful property is invertibility. The inverse of XOR is XOR itself.

This means that to undo an XOR operation that was computed on two values $a$ and $b$ we can XOR the result with $a$ to recover the value of $b$ or we can XOR the result with $b$ to recover the value of $a$.

To get a better understanding as to why this is useful in Cryptography, let’s assume that we have a plaintext $p$ and a key $k$.

Our ciphertext $c$ is the result of computing $p \oplus k$.

Looking closer, we can see that the encryption algorithm is $\oplus$.

Given our ciphertext $c$ and the key $k$ how do we recover the plaintext $p$? We just XOR the ciphertext $c$ with the key $k$ again.

So the decryption algorithm is XOR as well.

This beneficial property is often used in symmetric ciphers such as the stream cipher ChaCha20 which uses $\oplus$ during the encryption and decryption phase.

Perfectly Balanced

Another, very useful property of XOR is that it’s perfectly balanced.

Let’s take a look at the truth table from above to see what it means for XOR to be perfectly balanced.

Here we’ve modified the table slightly and renamed $a$ to $p$ and $b$ to $k$. The reason being that we assume that $p$ is a plaintext bit and $k$ is a key bit. $p \oplus k$ is therefore the resulting ciphertext bit.

If we work under the assumption that the key generation algorithm produces a perfectly random value for $k$ (i.e. there’s a 50% chance that $k$ is either $0$ or $1$), we can see that this randomness is carried through to the ciphertext as its bit value is also either $0$ or $1$ with exactly 50% probability (again, depending on the key bit value $k$).

The exact same is true for when the plaintext bit $p$ is $1$.

So in conclusion we can see that if we get access to a ciphertext bit then there’s an exactly 50% chance that the input bit was either $0$ or $1$.

Therefore XOR is perfectly balanced.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Wikipedia - Exclusive Or
• Wikipedia - XOR Gate
• Wikipedia - Truth Table