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