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
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][1]. Conversely, for any pair of integers [math]\displaystyle{ (n,m) }[/math] satisfying this hypothesis, there exists a bent [math]\displaystyle{ (n,m) }[/math]-function.
- ↑ Nyberg K. Perfect nonlinear S-boxes. InWorkshop on the Theory and Application of of Cryptographic Techniques 1991 Apr 8 (pp. 378-386). Springer, Berlin, Heidelberg.