Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?
share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
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. –  Dennis 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  
γ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. –  Dennis Dec 30 '13 at 15:00
add comment

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.

share|improve this answer
1  
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$. –  AnotherTest Dec 28 '13 at 17:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.