Bent Functions

From Boolean

Background and Definition

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

nl(F)≤2n−1−2n/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 DaF for a≠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≤n/2[1]. Conversely, for any pair of integers (n,m) satisfying this hypothesis, there exists a bent (n,m)-function.

  1. ↑ 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.