# 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 π₯βπ½2π, ${\displaystyle \sum _{a,b\in \mathbb {F} _{2}^{n}}(-1)^{D_{a}D_{b}f(x)}=2^{n}}$,
• 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 π½2π.

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

${\displaystyle W_{f}(u)=2^{n/2}(-1)^{{\tilde {f}}(u)},}$

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:
${\displaystyle n/2-d^{\circ }f\geq {\frac {n/2-d^{\circ }{\tilde {f}}}{d^{\circ }{\tilde {f}}-1}}}$
• Obviously, no affine function can be bent.
• When π is quadratic, then it is affine equivalent to the function
${\displaystyle x_{1}x_{2}\oplus x_{3}x_{4}\oplus \ldots \oplus x_{n-1}x_{n}\oplus \epsilon ,(\epsilon \in \mathbb {F} _{2}).}$
• The characterisation of cubic bent functions has been done for small dimensions (πβ€8).

# Constructions

## The Maiorana-McFarland Construction

For π=2π, π½2π={(π₯,π¦) : π₯,π¦βπ½2π}, π is of the form

${\displaystyle f(x,y)=x\cdot \pi (y)\oplus g(y),}$

where π is a permutation of π½2π and π is any π-variable Boolean function. Any such function is bent (the bijectivity of π is a necessary and sufficient condition). The dual function is ${\displaystyle {\tilde {f}}(x,y)=y\cdot \pi ^{-1}(x)\oplus g(\pi ^{-1}(x))}$.

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