2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Please revise your question and explain more about the concept of ANF or make a link for this subject. Tell more about the application of ANF in cryptography and using examples, clear your questions for users. In fact, to receive a good answer please ask your question properly. Thanks $\endgroup$
    – user3571
    Commented Sep 9, 2021 at 5:37
  • 1
    $\begingroup$ 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? $\endgroup$
    – fgrieu
    Commented Sep 9, 2021 at 5:50

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ There is a minor typo at line 2 (sage: F = GF(2**n) should be in a new line). $\endgroup$
    – hola
    Commented Apr 15, 2023 at 13:09
  • $\begingroup$ Anyway, @Fractalice, I could not understand in which part did your code use the information that $\gcd(k, n) = 1$. Did I miss something? $\endgroup$
    – hola
    Commented Apr 15, 2023 at 13:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Fractalice
    Commented Apr 16, 2023 at 16:46
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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