i cant understand the meaning and the difference between linearity and affine and non linearity equations and what is the meaning of the free term in affine form and how it make the equation non linear and why this form "affine" used?


Let $x_k$ be binary variables and $a_k$ be binary constants. So all arithmetic is modulo 2. Then $$f(x_1,\ldots,x_n)=a_0\oplus a_1 x_1\oplus \ldots\oplus a_n x_n$$ is an affine expression if $a_0\neq 0$ and is a linear expression otherwise.

An affine equation, e.g., would be $$a_0\oplus a_1 x_1\oplus \ldots\oplus a_n x_n=0$$ where $a_0\neq 0.$ This equation is called a linear equation if $a_0=0.$

Any expression with a term of the form $x_i x_j$ for $i\neq j$ is a nonlinear expression (note that $x_i^2=x_i$ modulo 2 so we need $i\neq j.$

However be careful, cryptographic terminology can be confusing.

The nonlinear order of an expression is the maximal $k$ for which a term $x_{i_1} \cdots x_{i_k}$ occurs in it.

The nonlinearity of an expression $f(x_1,\ldots,x_n)$ is its minimum Hamming distance from the set of affine functions as $(x_1,\ldots,x_n)$ varies over its $2^n$ values and is computed via the Walsh-Hadamard transform.

  • $\begingroup$ That expression is affine even if $\: a_{\hspace{.02 in}0}\hspace{-0.03 in} = 0 \;$. $\;\;\;\;$ $\endgroup$ – user991 Jul 22 '15 at 0:15
  • $\begingroup$ @RickyDemer: Which one? $\endgroup$ – kodlu Jul 22 '15 at 0:19
  • $\begingroup$ The expression with $\oplus$s. $\;$ $\endgroup$ – user991 Jul 22 '15 at 0:20
  • $\begingroup$ first i want to thank you, then i want to know the maths meaning of a0, is this mean a straight line doesn't path the origin, or the equation doesn't achieve the zero condition? $\endgroup$ – bassam Jul 22 '15 at 0:27
  • $\begingroup$ I have fixed an error in the definition of an affine equation. And yes, affine means (for binary) the line does not pass through zero which is the same as the equation is equal to 1 not zero. $\endgroup$ – kodlu Jul 23 '15 at 5:29

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