Truth table of Maiorana McFarland type functions

asked 2021-08-02 22:03:56 +0200

Kenan DOGAN gravatar image

updated 2022-04-14 10:56:12 +0200

FrédéricC gravatar image

I want to find truth table and Algebraic Normal Form of a Maiorana McFarland type bent function with the support set. I do a sample function by hand from $F_4$x$F_4$ to $F_2$ such that the Finite Field $F_4$ is generated by the irreducible polynomial $a^2+a+1$ so that $a^2=a+1$.

$F_4$x$F_4$={(0,0),(0,1),(0,a),(0,a+1),(1,0),(1,1),(1,a),(1,a+1),(a,0),(a,1),(a,a),(a,a+1),(a+1,0),(a+1,1),(a+1,a),(a+1,a+1)}

Take the support set as S={(0,a+1),(1,a),(a,a+1),(a+1,0),(a+1,1),(a+1,a+1)}. I want to find the boolean function which has the support set S. The whole elements of $F_4$x$F_4$ and the corresponding elements of $F_2^4$ and Truth Table results are given in table. 0=00, 1=01, a=10, a+1=11 $$ \left[ \begin{array}{c|c|c} (0,0) & (00,00)& 0000 & 0\newline (0,1) &(00,01)&0001& 0 \newline (0,a) & (00,10)&0010 & 0 \newline \textbf{(0,a+1)} & (00,11)& 0011 & \textbf{1} \newline (1,0) & (01,00)&0100 & 0 \newline (1,1) &(01,01)& 0101 & 0 \newline \textbf{(1,a)} & (01,10)& 0110 & \textbf{1} \newline (1,a+1) & (01,11)& 0111 & 0 \newline (a,0) & (10,00)& 1000 & 0 \newline (a,1) & (10,01)& 10001 & 0 \newline (a,a) & (10,10)&1010 & 0 \newline \textbf{(a,a+1)} & (10,11)& 1011 & \textbf{1} \newline \textbf{(a+1,0)} & (11,00)& 1100 & \textbf{1} \newline \textbf{(a+1,1) } & (11,01)&1101 & \textbf{1} \newline (a+1,a) & (11,10)&1110 & 0 \newline \textbf{(a+1,a+1) } & (11,11)& 1111 & \textbf{1} \end{array} \right] $$ By the truth table, I can find whether this function is bent or not with the codes below:

 from sage.crypto.boolean_function import BooleanFunction

 B = BooleanFunction([0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1])

 P = B.algebraic_normal_form()

 print (P)

 f = BooleanFunction(P)

 print ("Bent         :", f.is_bent())

The problem is I need the SAGE program that finds the truth table if I have the support set of a function from $F_{64}$x$F_{64}$ to $F_2$.

 FF=FiniteField(64,"a")
 a=FF.gen()

 tr= [a, a^2, a^4, a^5, a^5 + a^4 + a^2 + a + 1, a^5 + a^4 + 1, a^4 + a + 1, a^5 + a^2 + a, a^2 + a + 1, a^5 + a^4 + a^2, a^5 + a^4 + a, a^5 + a^2 + 1, a^4 + a^2 + 1, a^5 + a + 1, a^4 + a^2 + a, 1, a^3, a^5 + a^3 + 1, a^3 + a^2 + a, a^4 + a^3 + a^2, a^5 + a^4 + a^3, a^3 + a^2 + 1, a^4 + a^3 + a, a^5 + a^4 + a^3 + a^2 + 1, a^4 + a^3 + 1, a^4 + a^3 + a^2 + a + 1, a^5 + a^4 + a^3 + a^2 + a, a^5 + a^3 + a, a^5 + a^3 + a^2 + a + 1, a^3 + a + 1, a^5 + a^3 + a^2, a^5 + a^4 + a^3 + a + 1]

 FF=[x for x in FF]

 U_s=[]

 for s in tr:

     for x in FF:

         if x!=0:

             U_s.append(x,s*x^5)

I generated the support set U_s in $F_{64}$x$F_{64}$ . How can I find the truth table of the corresponding function?

Thanks in advance.

edit retag flag offensive close merge delete

Comments

1

As expressed, the computation of $U_s$ is questionable, because you have two loops using the same x variable. Do you mean :

for s in tr:
     for x in FF:
         if x!=0:
             U_s.append([(x,s*x^5)])

( more Pythonically expressed as :

for s in tr:
    U_s.append([(x,s*x^5) for x in set(FF)-{FF(0)}])

by the way) or something else ?

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2021-08-05 12:00:02 +0200 )edit

You are right. I deleted it.

Kenan DOGAN gravatar imageKenan DOGAN ( 2021-08-28 10:20:55 +0200 )edit