Score:0

Crypto

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

mathd

1/9/23, 5:25 AM

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?

1 + 2

s-boxes

finite-field

user3571

1/9/23, 5:37 AM

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

fgrieu

1/9/23, 5:50 AM

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](https://en.wikipedia.org/wiki/Algebraic_normal_form#Recursively_deriving_multiargument_Boolean_functions)?

Score:1

Crypto

kodlu

1/9/23, 6:07 AM

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

0 + 0

Score:0

Crypto

Fractalice

1/10/23, 6:39 AM

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 = 1sage: 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.

0 + 0

hola

4/15/24, 1:09 PM

There is a minor typo at line 2 (`sage: F = GF(2**n)` should be in a new line).

hola

4/15/24, 1:09 PM

Anyway, @Fractalice, I could not understand in which part did your code use the information that $\gcd(k, n) = 1$. Did I miss something?

Fractalice

4/16/24, 4:46 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: รูปแบบปกติเกี่ยวกับพีชคณิตของฟังก์ชันใน $\operatorname{GF}(2^{n})$

RO: Forma normală algebrică a unei funcții în $\operatorname{GF}(2^{n})$

RU: Алгебраическая нормальная форма функции в $\operatorname{GF}(2^{n})$

VI: Dạng chuẩn đại số của một hàm trong $\operatorname{GF}(2^{n})$

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.