The following statement is from a paper (Partitions in the S-Box of Streebog and Kuznyechik) about S-Boxes:

For all $ x \in \operatorname{GF}(2^{n})$, it holds that $x^{2^{n}} \oplus x = 0$.
If $n= 2m$ then we define the trace from $\operatorname{GF}(2^{2m}) \to \operatorname{GF}(2^{m})$ as the function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$.

I don't understand why this works for all $ x \in \operatorname{GF}(2^{2m})$. Why is it safe to say that this operation ends in the subfield $\operatorname{GF}(2^{m})$?

  • $\begingroup$ @Aleph could you explain that further please? $\endgroup$ – winklerrr Jun 24 '19 at 21:07
  • 2
    $\begingroup$ This isn't a question about cryptography. Anyway, the answer is because $(x^{2^m} + x)^{2^m} = x^{2^m} + x$ for $x \in \mathbb{F}_{2^{2m}}$. I'd recommend reading some introductory lecture notes/book on (finite) fields though. $\endgroup$ – Aleph Jun 24 '19 at 21:10
  • 1
    $\begingroup$ Because $x^{2^{2m}} = x$ in $\mathbb{F}_{2^{2m}}$. The proper explanation would be that the Galois group of $\mathbb{F}_{2^{2m}} / \mathbb{F}_{2^{m}}$ consists of the identity map and $x \mapsto x^{2^m}$... $\endgroup$ – Aleph Jun 24 '19 at 21:12

All elements of $\text{GF}(q)$ are roots of $x^q-x$. In fact, this is a litmus test for determining membership in $\text{GF}(q)$: when working in an extension field of $\text{GF}(q)$, say $\text{GF}(q^m)$, we can determine whether an $\alpha$ is a member of $\text{GF}(q)$ by computing $\alpha^q$ and checking whether the result equals $\alpha$ or not.

So, in $\text{GF}(2^n)$, $\alpha^{2^n} - \alpha = 0$, and if we remember that addition and subtraction are the same operation in fields of characteristic $2$ and that this operation is often denoted by $\oplus$, we have that $x^{2^n}\oplus x = 0$.

The trace function from $\text{GF}(q^k)$ to $\text{GF}(q)$ is defined as $$\operatorname{Tr}(x) = x + x^q + x^{q^2} + \cdots + x^{q^{k-1}}.$$ Verify that for all $x \in \text{GF}(q^k)$, $\operatorname{Tr}(x)$ belongs to $\text{GF}(q)$. (Hint: apply the litmus test). So for the special case when $k=2$, the trace function from $\text{GF}(q^2)$ to $\text{GF}(q)$ is just $\operatorname{Tr}(x) = x + x^q$. I will leave it to the OP see what happens when $q$ equals $2^m$ and whether the statements of the S-Box book are true or not.

  • $\begingroup$ Thank you! This helps me a lot! Also your answer here is a very good explanation of this topic! $\endgroup$ – winklerrr Jun 25 '19 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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