Bent Functions

Background and Definition

The covering radius bound states that the nonlinearity [math]\displaystyle{ nl(F) }[/math] of any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] satisfies

[math]\displaystyle{ nl(F) \le 2^{n-1} - 2^{n/2 - 1}. }[/math]

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 [math]\displaystyle{ (n,m) }[/math]-function is at most [math]\displaystyle{ n/2 }[/math].

An [math]\displaystyle{ (n,m) }[/math]-function is bent if and only if all of its derivatives [math]\displaystyle{ D_aF }[/math] for [math]\displaystyle{ a \ne 0 }[/math] are balanced. In this sense, bent functions are also referred to as perfect nonlinear (PN) functions.

Bent (PN) [math]\displaystyle{ (n,m) }[/math]-functions exist only for [math]\displaystyle{ n }[/math] even and [math]\displaystyle{ m \le n/2 }[/math]. Conversely, for any pair of integers [math]\displaystyle{ (n,m) }[/math] satisfying this hypothesis, there exists a bent [math]\displaystyle{ (n,m) }[/math]-function.