# What are linear and non-linear elements in cryptography?

I was reading this answer, How secure is XOR for encryption, and it stated that XOR's aren't good for securing messages as they are linear in Nature. And therefore should be paired with some non-linear elements like Substitution box to provide strength to the encryption.

My question is, what are linear/Non-linear elements, in context of cryptography? And what are advantages and disadvantages of each over the other.

A mathematical function $$f$$ is linear if it is of the form $$f(t) = c + g(t)$$ where $$c$$ is a constant and $$g$$ has the property that $$g(a + b) = g(a) + g(b)$$. (Strictly speaking, in math one usually considers only $$g$$ to be linear and $$f$$ to be merely affine, but we don't make that distinction here.) We also say that a function $$\phi(s, t)$$ of two arguments is bilinear, or again just linear, if for each $$s_0$$ and $$t_0$$, the functions $$t \mapsto \phi(s_0, t)$$ and $$s \mapsto \phi(s, t_0)$$ are linear.

Exercise. Prove that the function $$(s, t) \mapsto s + t$$ is bilinear.

If we're talking about real numbers, like 0, −3, 1/48, $$\pi$$, etc., linear functions are of the form $$f(x) = mx + b$$ for constants $$m$$ and $$b$$, which you may recognize as the equation of a (nonvertical) line. But we don't have to talk about real numbers; we can consider integers too, or even the remainders of integers after dividing by 2 (‘modulo 2’), where $$0 + 0 = 0$$, $$0 + 1 = 1$$, $$1 + 0 = 1$$, and $$1 + 1 = 0$$. The linear functions in this case are still of the form $$f(x) = mx + b$$, but the only two possible values for $$m$$ and $$b$$ are 0 and 1, so there are only four such linear functions.

We can also do addition and multiplication of polynomials, or of matrices of higher dimensions. Each space has its own notion of linear functions, defined in terms of that space's notion of addition. Linear functions are easy to compute—and easy to invert, or at least partially invert: in spaces where we have a notion of division (like rational numbers), we can recover $$x$$ from $$f(x)$$ by $$x = (f(x) - b)/m$$; in other spaces, like matrices, we have easy algorithms like Gaussian elimination to solve linear systems.

Suppose you have a string of bits, say 10110 or 00111. One way to interpret the bits is an integer, in this case 22 or 7 (in decimal). Another way is to interpret the bits as a polynomial with coefficients modulo 2, in this case $$x^4 + x^2 + x$$ or $$x^2 + x + 1$$. If we add these in their respective spaces and convert back to a string of bits, we get different answers:

$$\begin{gather} 22 +_\mathbb Z 7 = 29 \longrightarrow \mathtt{11101} \\ (x^4 + x^2 + x) +_2 (x^2 + x + 1) = x^4 + x + 1 \longrightarrow \mathtt{10011}. \end{gather}$$

Exercise. Why did the $$x^2$$ term disappear?

Here I have labeled the integer addition operation as $$+_\mathbb Z$$ and the polynomial modulo 2 addition operation as $$+_2$$. We could also write both sides of the equation as a string of bits; when we use $$+_\mathbb Z$$ and $$+_2$$, we may get different answers, as strings of bits:

\begin{align} \mathtt{10110} +_\mathbb Z \mathtt{00111} &= \mathtt{11101} \\ \mathtt{10110} +_2 \mathtt{00111} &= \mathtt{10001}. \end{align}

Exercise. Is there another name for $$+_2$$?

Exercise. Find two bit strings $$s$$ and $$t$$ such that $$s +_\mathbb Z t = s +_2 t$$.

Although $$+_\mathbb Z$$ is linear (or, more precisely, bilinear) in integer addition, it is not linear in polynomial modulo 2 addition—in other words, although, e.g., $$t \mapsto s_0 +_\mathbb Z t$$ is linear over $$+_\mathbb Z$$ meaning it is of the form $$t \mapsto c +_\mathbb Z g(t)$$, specifically with $$c = s_0$$ and $$g(t) = t$$, this function is not of the form $$c +_2 g(t)$$ for any $$c$$ or $$g$$. Conversely, $$+_2$$ is linear in polynomial modulo 2 addition but not in integer addition.

In other words, xor is linear in polynomial modulo 2 addition, but not in integer addition; conversely, integer $$+$$ is linear in integer addition, but not in polynomial modulo 2 addition. When you combine the two—e.g., consider the function $$(u, v, w) \mapsto (u +_\mathbb Z v) +_2 w$$—the result is a function that is nonlinear in both spaces, which means it does not admit any neat algebraic simplification or inversion like $$(f(x) - b)/m$$ or Gaussian elimination. This in turn means that cryptanalysis can't take advantage of neat algebraic simplification or inversion, and so may be much harder.

• The Maths required to understand this answer, is beyond my scope. I am not good at maths (pardon me for that), can you please short this down to something more like a definition, a statement or something having more influence of cryptography rather then maths. (I can only understand modulo 2, xor, or primitive maths) – Vasu Deo.S May 31 '19 at 15:04
• @VasuDeo.S If the math in this answer is beyond your scope, may I suggest working to broaden your scope a little bit? These are basics that you will need if you ever want to do cryptography. Key words are: functions, groups, fields, polynomials, modulo. Hint: xor actually figures prominently in this story under a different name. – Squeamish Ossifrage May 31 '19 at 15:08
• Sure I will. But for now, isn't there any other answer which does not involve maths? Like a short answer of what a linear/Non linear element is that without maths? – Vasu Deo.S May 31 '19 at 15:13
• @VasuDeo.S No. Linear and nonlinear are mathematical concepts. It's like you're asking what a noun and a verb are, but without using words. – Squeamish Ossifrage May 31 '19 at 15:22
• @VasuDeo.S Math is the language we use to talk about precise ideas. Instead of avoiding the language and asking to be spoon-fed, I suggest you work on learning the language so you can follow everyone else. – Squeamish Ossifrage May 31 '19 at 15:28

Xor is linear because its answers are predicted and they’re 4 possible outcomes of this. So this can be broken or breached by brute force of some other techniques. On the other hand, non linear operation includes linear plus other s-boxes techniques which is based on some finite-field inverse and some shuffling.

• Any boolean function of two inputs has four outcomes depending on the inputs; xor is not unique in this respect. This doesn't address what linear means or how xor is linear while S-boxes are (sometimes!) nonlinear. – Squeamish Ossifrage May 31 '19 at 15:30