# Why xor is a linear operation but ordinary adding is not

I'm new in cryptography and try to read some articles in this field. Many of these articles talk about non-linear S-boxes, and nothing more on what they mean by their non-linearity.

I have a simple question which I think will guide me through my problem:

• why is the XOR operation is linear, but ordinary adding (+) not‽
• what is the definition of linearity?
-

What is the definition of linearity?

Linearity is defined for maps between vector spaces. If you have a field $F$ and two vector spaces $U$ and $V$ over the field $F$, a map $$T:U\rightarrow V$$ is said to be linear if $$T(\gamma_1\odot u_1\oplus\gamma_2\odot u_2)=\gamma_1 \odot T(u_1)\oplus\gamma_2\odot T(u_2)$$ whenever $\gamma_1,\gamma_2\in F$ and $u_1,u_2\in V$. Here, $\oplus$ and $\odot$ denote the addition of vectors and their multiplication by a scalar (element of the field).

For different vector spaces, you get different linear maps.

Lets consider $U$ as the set of all 8-bit integers, i.e., the integers between $0$ and $255$. Each of those can be expressed as a string of exactly 8 bits, using the base-2 numeral system. For example, $13$ becomes $00001101$, since $$0\cdot2^7+0\cdot2^6+0\cdot2^5+0\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0=8+4+1=13.$$

A way of looking at $U$ is considering its elements to be vectors of $\{0,1\}^8$. For example, the number $13$ becomes the vector $(0,0,0,0,1,1,0,1)$. The natural way of defining the sum of two vectors in this case is addition modulo $2$, component by component. This results in the sum being the exclusive OR of both addends. When $F=\{0,1\}$, $U$ becomes a vector space over $F$.

Why is the XOR operation is linear, but ordinary adding (+) not‽

Because the sum in the vector space is exclusive OR, not modular addition. The mapping $x\mapsto x\oplus c$ (here, $\oplus$ is exclusive OR) is actually an affine transformation, which are oftentimes called linear outside linear algebra.

-
Nitpick: the integers with ordinary addition modulo 256 are not a vector space over any finite field. In fact, they're not a vector space at all, although they are an abelian group, and therefore a module over the ring of integers. –  Ilmari Karonen Dec 28 '13 at 18:36
Right, scalar multiplication isn't distributive over field addition. –  sudo Dec 28 '13 at 19:00
wow thanks, that was really helpful Dennis. I have another mini question: scalars γ1 and γ2 in your definition of linearity, can just get values 0 and 1, is it right ?! –  Shnd Dec 30 '13 at 14:23
γ1 and γ2 can be any scalar, i.e, any element of the field F. In the example of the 8-bit integers, the only scalars are 0 and 1, yes. But in general, F could be any field, e.g., the set of all rational, real or complex numbers. –  sudo Dec 30 '13 at 15:00

They are both linear, but in different algebraic Groups. Which is to say, xor is linear in any finite field of characteristic 2, while 'ordinary' addition is linear in the infinite field of the Real numbers. Addition modulo $n$ (which is more cryptologically significant than addition over the Reals) is also a linear operation, but in the ring of integers $\mathbb{Z}_n$.

A linear function is simply one that can be accurately described by an algebraic equation (in some particular algebra or another) where none of the terms are of degree greater than 1.

So the xor of two variables can be accurately described by a linear algebraic equation in a finite field of characteristic 2. But there is no linear equation in the algebra of $\mathbb{Z}_n$ (for $n > 2$) that can accurately describe the xor of two variables. Conversely, the addition modulo $n$ ($n > 2$) of two variables can be accurately described by a linear equation in $\mathbb{Z}_n$, but not by a linear equation in any finite field of characteristic 2.

If none of that made any sense to you, that's OK. You just need to read up about Abstract Algebra, and Fields, Rings and Groups. It's a fascinating and beautiful area of mathematics, and much of cryptography will make no sense without at least some understanding of it.

-
Personally, I would associate linear mappings with vector spaces. That is, as a homomorphism between 2 vector spaces (regarded as abelian groups). With the additional property that $m(\alpha x) = \alpha m(x)$ for $\alpha \in F$. –  Aleph Dec 28 '13 at 17:27