At https://eprint.iacr.org/2013/455.pdf page 8, lemma 1 defines the following map from $\{0,1\}^8$ to itself: $$ \varphi : x \mapsto \bigoplus_{a=0}^{15}{g(x \oplus a)} $$
The paper does not explictly state the notation, so the following may be wrong, but I assume that (if a different interpretation makes more sense, feel free to correct these):
- $\oplus$ is field addition / vector addition (since the field is $GF(2^8)$, this is the same as component-wise xor if you represent the polynomials by the coefficents as bits)
- Perhaps then $\{0,1\}^8$ represents the vector space of dimension 8 over the field $GF(2)$, since they use $\mathbb{F}_{2^8}$ elsewhere in the paper to denote the field $GF(2^8)$?
- I have no idea what $D_1$, $D_2$, $D_4$ and $D_8$ are supposed to be (this is their only use in the paper)
and then claims that:
The map $\varphi$ defined in Lemma 1 is a 4th-order derivative of the function $g$ (specifically $\varphi=D_1D_2D_4D_8(g)$)
How do they conclude that? There are no restrictions placed upon $g$, it is just an arbitrary map?
The following is partly educated guessing, but it fits. Basically it is just about interpreting everything carefully. Here comes the TL; DR; -version.
Assuming that:
With this definition we do get the formula $$ D_1D_2D_4D_8(g):x\mapsto \sum_{a=0}^{15}g(x\oplus a). $$ This is just a manifestation of the fact that, when viewed as above, the set $W=\{0,1,2,\ldots,15\}$ is a subgroup of $V$. It is actually a subspace spanned by the linearly independent elements $1$, $2$, $4$ and $8$.
To see this we first observe that $$ D_1(g):x\mapsto g(x\oplus1)+g(x)=\sum_{a=0}^1g(x\oplus a). $$ Then $$ \begin{aligned} D_1D_2(g):x&\mapsto D_2(g)(x\oplus1)+D_2(g)(x)\\ &=\left(g((x\oplus1)\oplus2)+g(x\oplus1)\right)+\left(g(x\oplus2)+g(x)\right)\\ &=g(x\oplus3)+g(x\oplus1)+g(x\oplus2)+g(x)\\ &=\sum_{a=0}^3g(x\oplus a). \end{aligned} $$ Repeating the dose $$ \begin{aligned} D_1D_2D_4(g):x&\mapsto \sum_{a=0}^3D_4(g)(x\oplus a)\\ &=\sum_{a=0}^3\big(g(x\oplus a\oplus4)+g(x\oplus a)\big)\\ &=\sum_{a=0}^7g(x\oplus a). \end{aligned} $$ And one more repetition then gives the claim.
To understand why $D_{2^n}$ are called derivations we need to break the functions into components. Any function $g:V\to V$ can be written using the components $$ g(x)=(g_0(x),g_1(x),\ldots,g_7(x)), $$ where the components $g_i:V\to\Bbb{F}_2$ are all boolean functions in the variables $x_0,x_1,\ldots,x_7$. Any such boolean function can be uniquely written as a polynomial in the unknowns $x_i$ ranging over $\Bbb{F}_2$. Remember that we only need to use terms $x_{i_1}x_{i_2}\cdots x_{i_k}$ with $i_1<i_2<\cdots<i_k$ because the polynomials $x_i^2$ and $x_i$ give the same boolean function.
We obviously have $$ g_i(x\oplus 2^n)=g_i(x_0,x_1,\ldots,x_{n-1},x_n+1,x_{n+1},\ldots,x_7).\tag{1} $$ The following observation is the key: $$ D_{2^n}(g_i)(x)=\frac{\partial g_i}{\partial x_n}(x).\tag{2} $$ Everything in sight is linear, so it suffices to prove $(2)$ for each monomial $g_i(x)=x_{i_1}x_{i_2}\cdots x_{i_k}$. Here if $n$ does not appear among the indices $i_1,\ldots, i_k$ we have, by $(1)$, $g_i(x\oplus2^n)=g_i(x)$ for all $x\in V$. In this case we have the constant function zero on both sides of $(2)$.
On the other hand, if $i_t=n$, then $$ \begin{aligned} D_{2^n}(g_i)(x)&=g_i(x\oplus2^n)+g_i(x)\\ &=g_i(x_0,x_1,\ldots,x_n+1,\ldots,x_7)+g_i(x_0,\ldots,x_7)\\ &=x_{i_1}\cdots (x_{i_t}+1)\cdots x_{i_k}+x_{i_1}x_{i_2}\cdots x_{i_k}\\ &=x_{i_1}\cdots x_{i_{t-1}} x_{i_{t+1}}\cdots x_{i_k}, \end{aligned} $$ so $(2)$ holds in this case as well. Q.E.D.
This then implies the last claim in the form $$ D_1D_2D_4D_8(g)=\left(\frac{\partial^4g_i}{\partial x_0\partial x_1\partial x_2\partial x_3}\right)_{i=0}^7. $$