# Bent Boolean Functions

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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𝑛, $\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

$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:
$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
$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

$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 ${\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.