# Bent Functions

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

# Background and Definition

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

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

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

Bent (PN) ${\displaystyle (n,m)}$-functions exist only for ${\displaystyle n}$ even and ${\displaystyle m\leq n/2}$[1]. Conversely, for any pair of integers ${\displaystyle (n,m)}$ satisfying this hypothesis, there exists a bent ${\displaystyle (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.