Bent Boolean Functions

An 𝑛-variable Boolean function 𝑓 (for even 𝑛) is called bent if its distance to the set of all 𝑛-variable affine functions (the nonlinearity of 𝑓) equals 2^𝑛-1-2^𝑛/2-1.

Equivalently, 𝑓 is bent if

• 𝑊_𝑓(𝑢) takes only the values ±2^𝑛/2,
• 𝑊_𝑓(𝑢)≡2^𝑛/2 (mod 2^𝑛/2+1),
• its distance to any affine function equals 2^𝑛-1±2^𝑛/2-1,
• for any nonzero element 𝑎 the Boolean function 𝐷_𝑎𝑓(𝑥)=𝑓(𝑥+𝑎)⊕𝑓(𝑥) is balanced,
• for any 𝑥∈𝔽₂^𝑛, [math]\displaystyle{ \sum_{a,b\in\mathbb{F}_2^n}(-1)^{D_aD_bf(x)}=2^n }[/math],
• the 2^𝑛×2^𝑛 matrix 𝐻=[(-1)^{𝑓(𝑥+𝑦)}]_{𝑥,𝑦∈𝔽2^𝑛} is a Hadamard matrix (i.e. 𝐻×𝐻^𝑡=2^𝑛𝐼, where 𝐼 is the identity matrix),
• the support of 𝑓 is a difference set of the elementary Abelian 2-group 𝔽₂^𝑛.

Bent functions are also called perfect nonlinear functions.

The dual of a bent 𝑓 function is also a bent function, where the dual is defined as

[math]\displaystyle{ W_f(u)=2^{n/2}(-1)^{\tilde{f}(u)}, }[/math]

and its own dual is 𝑓 itself.

Bent functions and algebraic degree

• For 𝑛 even and at least 4 the algebraic degree of any bent function is at most 𝑛/2.
• The algebraic degree of a bent function and of its dual satisfy the following relation:

[math]\displaystyle{ n/2-d^\circ f\ge\frac{n/2-d^\circ\tilde{f}}{d^\circ\tilde{f}-1} }[/math]

• Obviously, no affine function can be bent.
• When 𝑓 is quadratic, then it is affine equivalent to the function

[math]\displaystyle{ x_1x_2\oplus x_3x_4\oplus\ldots\oplus x_{n-1}x_n\oplus\epsilon, (\epsilon\in\mathbb{F}_2). }[/math]

• The characterisation of cubic bent functions has been done for small dimensions (𝑛≤8).

Constructions

The Maiorana-McFarland Construction

For 𝑛=2𝑚, 𝔽₂^𝑛={(𝑥,𝑦) : 𝑥,𝑦∈𝔽₂^𝑚}, 𝑓 is of the form

[math]\displaystyle{ f(x,y)=x\cdot\pi(y)\oplus g(y), }[/math]

where 𝜋 is a permutation of 𝔽₂^𝑚 and 𝑔 is any 𝑚-variable Boolean function. Any such function is bent (the bijectivity of 𝜋 is a necessary and sufficient condition). The dual function is [math]\displaystyle{ \tilde{f}(x,y)=y\cdot\pi^{-1}(x)\oplus g(\pi^{-1}(x)) }[/math].

Such construction contains, up to affine equivalence, all quadratic bent functions and all bent functions in at most 6 variables.