Boolean Functions


Introduction


This page was created to exchange functions and computations developed in $\texttt{Sage}$ by A. Bapić for our research on Boolean functions.

The following lines need to be added to your $\texttt{Sage}$ notebook to support cryptographical functions that are available (for more info see Sage-BooleanFunctions and Sage-SBox).

from sage.crypto.sbox import SBox
from sage.crypto.boolean_function import BooleanFunction

Basic tools


Below we give some basic tools which will be used going onwards, including:

  • Walsh support of a Boolean function $f\in\mathcal{B}_n$
  • The inverse WHT given a Walsh spectra $w$ of length $2^n$
  • Checking wheather a Boolean function $f$ in odd dimension is semi-bent
  • Walsh spectra of a vectorial Boolean function $F$
  • Checking whether an $(n,m)$-function $F$ is AB, if $F$ is defined by a list of its coordinates (If $F$ is given in integer form, there is already an integrated function in Sage)
def walsh_support(f,n):
    w=BooleanFunction(f).walsh_hadamard_transform();
    l=len(w);
    V=VectorSpace(GF(2),n);
    ws=[];
    for v in V:
        i=ZZ(list(v),base=2);
        if(w[i] !=0):
            ws.append(vector(GF(2),v));
    return ws;

def inverseWHT(w,n):
    t=[];
    V=sorted(VectorSpace(GF(2),n));
    for u in V:
        s=0;
        for x in V:
            i=ZZ(list(x), base=2);
            s=s+w[i]*(-1)^(vector(u,GF(2))*vector(x,GF(2)));
        t.append((1-(2^(-n))*s)/2);
    return t;


def is_semibent(f,n):
    if((f.is_plateaued()) and (2^((n+1)/2) in f.walsh_hadamard_transform())):
        return True;
    else:
        return False;

def walsh_spectrum(F):
    n=len(F);
    S=[];
    for i in [1..2^n-1]:
        f=F.component_function(i);
        S=S+list(f.walsh_hadamard_transform());
    K=sorted(list(set(S)));
    return [[K[i],S.count(K[i])] for i in [0..len(K)-1]];
    
def isAB(M):
    T=list(transpose(matrix(M)));
    T1=[ZZ(list(x),base=2) for x in T];
    T1=SBox(T1);
    return T1.is_almost_bent();


$\mathcal{C}$ and $\mathcal{D}$ classes


The Maiorana-McFarland class $\mathcal{M}$ is the set of $m$-variable ($m=2n$) Boolean functions of the form

$$f(x,y)=x \cdot \pi(y)+ g(y), ox{ for all } x, y\in\mathbb{F}_2^n,$$

where $\pi$ is a permutation on $\mathbb{F}_2^n$, and $g$ is an arbitrary Boolean function on $\mathbb{F}_2^n$. From this class Carlet derived the $\mathcal{C}$ class of bent functions that contains all functions of the form

$$f(x,y) = x\cdot\pi(y)+ \mathbf{1}_{L^{\perp}}(x)$$

where $L$ is any linear subspace of $\mathbb{F}_2^n$, $\mathbf{1}_{L^{\perp}}$ is the indicator function of the space $L^{\perp}$, and $\pi$ is any permutation on $\mathbb{F}_2^n$ such that:

$(C)$ $\phi(a + L)$ is a flat (affine subspace), for all $a\in \mathbb{F}_2^n$, where $\phi:=\pi^{-1}$.

The permutation $\phi$ and the subspace $L$ are then said to satisfy the $(C)$ property, or for short _$(\phi,L)$ has property $(C)$_.

Another class introduced by Carlet, called $\mathcal{D}$, is defined similarly as $$f(x, y)=x\cdot\pi(y) + \mathbf{1}_{E_1}(x) \mathbf{1}_{E_2}(y)$$

where $\pi$ is a permutation on $\mathbb{F}_2^{n}$ and $E_1,E_2$ two linear subspaces of $\mathbb{F}_2^n$ such that $\pi(E_2)=E_1^{\perp}$.

We will define three $\texttt{Sage}$ functions:

  • the indicator function $\mathbf{1}_A(x)$ which will be denoted with $\texttt{ind(x,A)}$,
  • the trace function $Tr_m^n(x)$ denoted with $\texttt{tr(x,m,n)}$ and
  • the anihilator of a linear space $E$ of $\mathbb{F}_{2^m}$ denoted with $\texttt{dualSpace(E,m)}$.
#Fm=GF(2^m);
def ind(x,L):
    if x in L:
        return Fm.one();
    else:
        return Fm.zero();


def tr(x,m,n):
    return sum([x^(2^(i*m)) for i in [0..(n/m)-1]])


def dualSpace(E,m):
    Fm=GF(2^m);
    t=[];
    for x in Fm:
        b=0;
        for y in E:
            if (x*y).trace()==0:
                b=b+1;
        if b==len(E):
            t.append(x)
    return t;

Example: Let $m=9$ and $s=3$. Then $m/s$ is odd. Furthermore, for $d=284$ we have that $d(2^s+1) \mod (2^9-1)=1$. Let $U=\{1,\alpha,\alpha^2\}$ where $\alpha$ is a primitive element of $\mathbb{F}_{2^3}$ such that $\alpha^3+\alpha+1=0$.

For $L=\langle U\rangle$ we have that $(\pi^{-1},L)$ satisfies the $(C)$ property. Hence, the function $f:\mathbb{F}_{2^m}\times\mathbb{F}_{2^m}\to\mathbb{F}_2$ defined with $$f(x,y) = x\cdot\pi(y)+ \mathbf{1}_{L^{\perp}}(x)$$ is bent.

Fm=GF(2^9);
sFm=sorted(Fm);

p=Fm.primitive_element();
a=p^((2^9-1)/(2^3-1));
u=sFm[13];

Lperp=[x for x in Fm if ((x).trace()+1)*((x*a).trace()+1)==1];

f=[(x*y^284).trace()+ind(x,Lperp) for x in sFm for y in sFm];
f=BooleanFunction(f);
f.is_bent()

Example: Let $m=9$ and $s=3$. Then $m/s$ is odd. Furthermore, for $d=284$ we have that $d(2^s+1) \mod (2^9-1)=1$. Let $\alpha$ be a primitive element of $\mathbb{F}_{2^3}$ such that $\alpha^3+\alpha+1=0$.

For $E_2=\langle \alpha,\alpha^2 \rangle$ we have that $\pi(E_2)=E_2^{\perp}=E_1$. Hence, the function $f:\mathbb{F}_{2^m}\times\mathbb{F}_{2^m}\to\mathbb{F}_2$ defined with $$f(x,y) = x\cdot\pi(y)+ \mathbf{1}_{E_1}(x)\mathbf{1}_{E_2}(y)$$ is bent.

Fm=GF(2^9);
sFm=sorted(Fm);

p=Fm.primitive_element();
a=p^((2^9-1)/(2^3-1));

E2=[Fm.zero(),a^2,a+a^2,a];
E1=dualSpace(E2,9);

f=[(x*y^284).trace()+ind(x,E1)*ind(y,E2) for x in sFm for y in sFm];
f=BooleanFunction(f);
f.is_bent()

Let $\pi$ be a permutation on $\mathbb{F}_{2^m}$, $L\subset\mathbb{F}_{2^m}$ be a linear subspace of $\mathbb{F}_{2^m}$ such that $(\pi^{-1},L)$ satisfies the $(C)$ property, and let $E_1,E_2\neq \{0\}$ be two linear subspaces of $\mathbb{F}_{2^m}$ such that $\pi(E_2)=E_1^{\perp}$. Then the class of bent functions $f:\mathbb{F}_{2^m}\times\mathbb{F}_{2^m}\to\mathbb{F}_{2}$ containing all functions of the form
$$f(x,y)=Tr_1^m(x\pi(y))+a_0\mathbf{1}_{L^{\perp}}(x)+a_1\mathbf{1}_{E_1}(x)\mathbf{1}_{E_2}(y), ,; a_i \in \mathbb{F}_{2}$$ is called $\mathcal{CD}$ and is a superclass of $\mathcal{C}$ and $\mathcal{D}$.

Example: Let $m=9$ and $s=3$. Then $m/s$ is odd. Furthermore, for $d=284$ we have that $d(2^s+1) \mod (2^9-1)=1$. Let $U=\{1,\alpha,\alpha^2\}$ where $\alpha$ is a primitive element of $\mathbb{F}_{2^3}$ such that $\alpha^3+\alpha+1=0$.

For $L=\langle U\rangle$ we have that $(\pi^{-1},L)$ satisfies the $(C)$ property. For $E_2=\langle \alpha,\alpha^2 \rangle$ we have that $\pi(E_2)=E_2=E_1^{\perp}$. Hence, the function $f:\mathbb{F}_{2^m}\times\mathbb{F}_{2^m}\to\mathbb{F}_2$ defined with $$f(x,y) = x\cdot\pi(y)+ \mathbf{1}_{L^{\perp}}(x)+\mathbf{1}_{E_1}(x)\mathbf{1}_{E_2}(y)$$ is bent.

Below we give a program (depending if we are using vector space or finite field notation), which checks if $(\pi^{-1},L)$ satisfies the $(C)$ property. The permutations $\texttt{pi_inv}$ are given in their integer representation.

def shift_space(W,u):
    new=[];
    for v in W:
        new.append(vector(GF(2),v)+vector(GF(2),u));
    return new;

def is_flat(A,n):
    V=VectorSpace(GF(2),n);
    A1=V.subspace(A);
    if len(list(A1))==len(A):
        return True;
    else:
        return False;

def is_closed(F):
    C=Combinations([0..len(F)-1],2);
    C=C.list();
    G=Graph();
    for i in C:
        if F[i[0]]+F[i[1]] in F:
            G.add_edge([i[0],i[1]])
    if(len(G.clique_maximum())==len(F)):
        return True;
    else:
        return False;

def satisfiesC(pi_inv,L,n):
    t=[];
    Fn=GF(2^n);
    Vn=Fn.vector_space();
    for a in Vn:
        A=shift_space(L,a);
        F=[Vn(pi_inv[ZZ(list(x),base=2)]) for x in A];
        t.append[is_flat(F,n)];
    return t;

def satisfiesC_field(pi_inv,L,n,F):
    Fk=F;
    for a in Fk:
        if a!=Fk.zero():
            A=[pi_inv(a+L[i]) for i in [0..3]];
            B=[A[0]+A[i] for i in [0..3]];
            if (0 in B) and (is_closed(B)):
                return True;
            else:
                return False;

Inclusion/exclusion in $\mathcal{M}^{\#}$

A bent function $f$ in $n$ variables belongs to $\mathcal{M}^{\#}$ if and only if there exists an $\frac{n}{2}$-dimensional linear subspace $V$ of $\mathbb{F}_2^n$ such that the second-order derivatives $$ D_{a}D_{b}f(x)=f(x)\oplus f(x\oplus a)\oplus f(x\oplus b)\oplus f(x\oplus a\oplus b)$$ vanish for any $ a,b \in V$.

def is_in_MM(f,n):
    s=[];
    for a in [1..2^n-1]:
        for b in [a+1..2^n-1]:
            if set(ttab(f.derivative(a).derivative(b)))=={0}:
                s.append([a,b]);
    G=Graph();
    G.add_edges(s);
    cl=list(sage.graphs.cliquer.all_cliques(G,2^(n/2)-1,2^(n/2)-1));
    V=VectorSpace(GF(2),n);
    V1=sorted(V);
    b1=[V.subspace([V1[0]]+[V1[i] for i in s]) for s in cl];
    for K in b1:
        if len(K)==2^(n/2):
            return True;
    return False;

Example: The function $f\in \mathcal{D}_0$ defined by $f(x,y)=Tr_1^4(xy^7)+\delta_0(x)$ for $x,y\in\mathbb{F}_{2^4}$ is a bent function outside $\mathcal{M}^{\#}$.

Fm=GF(2^4);
sFm=sorted(Fm);

f=[(x*y^7).trace()+ind(x,[0]) for x in sFm for y in sFm];
f=BooleanFunction(f);
is_in_MM(f,8)
False

Duals of Boolean function

Depending on wheather $f$ is a bent or plateaued function, we have different notions of duals.

For a bent Boolean function $f$ defined on $\mathbb{F}_2^n$, its dual $f^{\star}$ is defined as a function from $\mathbb{F}_2^n$ to $\mathbb{F}_2$, for which it holds that $$(-1)^{f^{\star}( {x})}=2^{-\frac{n}{2}}W_f( {x}),\ \ {x}\in \mathbb{F}_2^n.$$ A standard way of defining the dual $\tilde{f}:\mathbb{F}_2^n\to\mathbb{F}_2$ of an $s$-plateaued Boolean function $f$ on $\mathbb{F}_2^n$ is as follows: $$\tilde{f}(x)=2^{-\frac{n+s}{2}}|W_f( {x})|,\ \ {x}\in\mathbb{F}_2^n.$$

def bent_dual(f,n): # f is bent
    t=[];
    w=f.walsh_hadamard_transform();
    for x in w:
        if x==2^(n/2):
            t.append(0);
        else:
            t.append(1);
    return BooleanFunction(t);

def stand_dual(f,n): # f is s-plateaued
    t=[];
    w=BooleanFunction(f).walsh_hadamard_transform();
    for x in w:
        if x==0:
            t.append(0);
        else:
            t.append(1);
    return BooleanFunction(t);

Let $S_f=v\oplus E=\{\omega_0,\ldots,\omega_{2^{k-s}-1}\} \subset \mathbb{F}_2^k$, for some $v \in \mathbb{F}_2^k$ and linear subspace $E=\{e_0,e_1, \ldots, e_{2^{k-s}-1}\}\subset \mathbb{F}^k_2$. For a function $f^{\star}:\mathbb{F}_2^{k-s}\rightarrow \mathbb{F}_2$ with $wt(f^{\star})=2^{k-s-1}\pm 2^{\frac{k-s}{2}-1}$, let the Walsh spectrum of $f$ be defined (by identifying $x_i \in \mathbb{F}_2^{k-s}$ and $e_i \in E$) as $W_f(u)= 2^{\frac{k+s}{2}}(-1)^{f^{\star}(x_i)}$ for $u= v\oplus e_i \in S_f$, and $W_f(u)=0$ otherwise. Then $f$ is an $s$-plateaued function if and only if $f^{\star}$ is a bent function on $\mathbb{F}^{k-s}_2$.

def plateFromBent(S,ttD,s,n):
    ws=[0 for i in [0..(2^n)-1]];
    j=0;
    for x in S:
        i=ZZ(list(x), base=2);
        ws[i]=2^((n+s)/2)*((-1)^(int(ttD[j])));
        j=j+1;
    return inverseWHT(ws);

$(P_U)$ property

We say that a Boolean function $g\in\mathcal{B}_n$ satisfies the property $(P_U)$ with the defining set $U\subseteq \mathbb{F}_2^n$ if $D_uD_vg\equiv 0$ for any $u,v\in U$. The program below finds the largest set $U$ for which this property is satisfied.

def Property_PTau(g,n):
    FF=sorted(GF(2^n));
    l=[sorted([x,y]) for x in [1..2^n-1] for y in [x+1..2^n-1] if g.derivative(x).derivative(y).algebraic_degree()==-1];
    G=Graph();
    G.add_edges(l);
    return G.cliques_maximum();

Functions $\varphi_u$ and $\psi_u$

For the definition and application of the functions $\varphi_u$ and $\psi_u$ we reffer to the following article of BPH - CLICK HERE.

def phi(u,fd,gd,Sf,Sg):
    L=[s for s in Sf if s not in intersection(Sf,Sg)];
    tt=[];
    for x in L:
        i=Sf.index(x);
        a=fd[i];
        v=vector(GF(2),u)+vector(GF(2),x);
        j=Sg.index(v);
        b=gd[j];
        tt.append((a+b)%2);
    return tt;

def psi(u,fd,gd,Sf,Sg):
    L1=intersection(Sf,Sg);
    tt=[];
    for x in L1:
        i=Sf.index(x);
        a=fd[i];
        v=vector(GF(2),u)+vector(GF(2),x);
        j=Sg.index(v);
        b=gd[j];
        tt.append((a+b)%2);
    return tt;

Constructions of 4-bent decompositions outside $\mathcal{M}^{\#}$

Let $g\notin \mathcal{M}^{\#}$ be a bent function in $n$ variables. For an arbitrary matrix $M\in GL(n,\mathbb{F}_2)$ and vector ${c}\in \mathbb{F}_2^n$, let $S_f=({c}\oplus \mathbb{F}_2^nM)\wr T_{t_1}\wr T_{t_2}$, where $t_1,t_2\in\mathcal{B}_{n}$ such that $g({x},{y})\oplus v_1t_1({x},{y})\oplus v_2t_2({x},{y})$ is bent for any $ v_1,v_2\in\mathbb{F}_2$, where $ {x},{y}\in\mathbb{F}_2^{n/2}$. Let $Q=\{\mathbf{0}_n\}\times \mathbb{F}_2^{2}=\{{q}_0,{q}_1,{q}_2,{q}_3\}$ and set $S_{f_i}={q}_i \oplus S_f$, for $i=0,\ldots,3$. Then, the functions $f_i \in \mathcal{B}_{n+2}$, constructed using Theorem 3.3 in HPWZ, with $S_{f_i}$ and $g$, are semi-bent functions on $\mathbb{F}_2^{n+2}$ with pairwise disjoint spectra. Moreover, the function $\mathfrak{f}\in\mathcal{B}_{n+4}$, whose restrictions are $\mathfrak{f}|_{{a}_i\oplus \mathbb{F}_2^{n+4}}=f_i$ (thus $\mathfrak{f}=f_1||f_2||f_3||f_4$), where ${a}_i\in{\mathbf{0}_{n+2}}\times \mathbb{F}_{2}^2$, is a bent function outside $\mathcal{M}^{\#}$.

Example: Below is an example in dimension $8$ for $t_1=t_2=\delta_0$ and $g\in\mathcal{D}_0\setminus\mathcal{M}^{\#}$.

def concat(tt):
    s=[];
    for x in tt:
        s=s+x;
    return BooleanFunction(s)

def delta(x):
    if x==0:
        return 1;
    else:
        return 0;


n=8;
G=GL(n,GF(2));
M=G.random_element();
E=VectorSpace(GF(2),n);
c=E.random_element();
S1=[c+M*x for x in E];
t1=[delta(x) for x in sorted(GF(2^4)) for y in sorted(GF(2^4))];

Sf=[list(S1[i])+[t1[i],t1[i]] for i in [0..255]]
Sf2=[vector(GF(2),x)+vector([0,0,0,0,0,0,0,0,0,1]) for x in Sf]
Sf3=[vector(GF(2),x)+vector([0,0,0,0,0,0,0,0,1,0]) for x in Sf]
Sf4=[vector(GF(2),x)+vector([0,0,0,0,0,0,0,0,1,1]) for x in Sf]
SF=[Sf,Sf2,Sf3,Sf4];

F=[];
g=[(x*y^7).trace()+delta(x) for x in sorted(GF(2^4)) for y in sorted(GF(2^4))]
f1=[(-1)^(g[i]) for i in [0..len(g)-1]];
S1=[[ZZ(list(x),base=2) for x in A] for A in SF]
for s1 in S1:
    t=[0 for i in [0..2^(10)-1]];
    j=0;
    for i in s1:
        t[i]=(2^((n+4)/2)*f1[j]);
        j=j+1;
    F.append(inverseWHT(t,10));

G=concat(F);
G=BooleanFunction(G);