# Algebraic Normal Form of a function in $\operatorname{GF}(2^{n})$

Consider the function $$f(x)=x^{2k+1}$$ in $$\operatorname{GF}(2^{n})$$ for $$n$$ odd and $$\gcd(k,n)=1$$, which is differentially 2-uniform function.

For $$n=3$$, $$k=1$$, I want to find the Algebraic Normal Form of the function. Is there a way?

• Anything wrong with the basic: assume a reduction polynomial for $\operatorname{GF}(2^n)$, use it to explicitly compute $f(x)$ as an $n$-bit bitstring for the mere $2^n$ values of $n$-bit bitstring $x$, makes that $n$ Boolean functions for $n$ Boolean arguments, find the ANF of each using some systematic method?
– fgrieu
Commented Sep 9, 2021 at 5:50

Note that you have $$n=3$$ output bits, each of them has its own ANF. Here's how to compute it with SageMath:

sage: from sage.crypto.sbox import SBox
sage: n = 3; k = 1
sage: F = GF(2**n)
sage: s = SBox([(F.fetch_int(x)**(2*k+1)).integer_representation() for x in range(F.order())])
sage: [s.component_function(2**i).algebraic_normal_form() for i in range(n)]
[x0 + x1*x2 + x1 + x2, x0*x1 + x0*x2 + x1, x0*x1 + x2]


This gives ANFs in order from least significant bit to most significant bit (this is defined by SageMath's convention for fetch_int/integer_representation).

In each ANF, the variable order is similar: x0 is the least significant input bit.

• There is a minor typo at line 2 (sage: F = GF(2**n) should be in a new line).
– hola
Commented Apr 15, 2023 at 13:09
• Anyway, @Fractalice, I could not understand in which part did your code use the information that $\gcd(k, n) = 1$. Did I miss something?
– hola
Commented Apr 15, 2023 at 13:09
• ANF can be computed for any Boolean function (i.e., 1-bit output). I suppose $gcd(k,n)=1$ is needed for the big (n-to-n) function to be a bijection. Even if it's not, the ANFs of its bits still exist. Commented Apr 16, 2023 at 16:46

As pointed out by @fgrieu the ANF is a multivariate polynomial representation. Usually over the binary base field, so $$n$$ binary variables are obtained. I suppose if $$n$$ is composite, it can also be defined over $$GF(2^m)$$ where $$m|n,$$ and $$m>1$$ but see no specific advantage to doing so.

There are two explicit answers related to the suggestion in the comment in the question below:

https://crypto.stackexchange.com/questions/47957/generate-anf-from-sbox/47959