Bent Functions

Background and Definition

The covering radius bound states that the nonlinearity $nl(F)$ of any $(n,m)$-function $F$ satisfies

$nl(F)\leq 2^{n-1}-2^{n/2-1}.$

A function is called bent if it achieves this bound with equality.

Properties

Since nonlinearity is a CCZ-invariant, CCZ-equivalence (and therefore also EA-equivalence and affine equivalence) preserves the property of a function of being bent.

The algebraic degree of any bent $(n,m)$-function is at most $n/2$.

An $(n,m)$-function is bent if and only if all of its derivatives $D_{a}F$ for $a\neq 0$ are balanced. In this sense, bent functions are also referred to as perfect nonlinear (PN) functions.

Bent (PN) $(n,m)$-functions exist only for $n$ even and $m\leq n/2$. Conversely, for any pair of integers $(n,m)$ satisfying this hypothesis, there exists a bent $(n,m)$-function.