Bent Boolean Functions

From Boolean Functions
Jump to: navigation, search

An 𝑛-variable Boolean function 𝑓 (for even 𝑛) is called bent if its distance to the set of all 𝑛-variable affine functions (the nonlinearity of 𝑓) equals 2𝑛-1-2𝑛/2-1.

Equivalently, 𝑓 is bent if

  • π‘Šπ‘“(𝑒) takes only the values Β±2𝑛/2,
  • π‘Šπ‘“(𝑒)≑2𝑛/2 (mod 2𝑛/2+1),
  • its distance to any affine function equals 2𝑛-1Β±2𝑛/2-1,
  • for any nonzero element π‘Ž the Boolean function π·π‘Žπ‘“(π‘₯)=𝑓(π‘₯+π‘Ž)βŠ•π‘“(π‘₯) is balanced,
  • for any π‘₯βˆˆπ”½2𝑛, ,
  • the 2𝑛×2𝑛 matrix 𝐻=[(-1)𝑓(π‘₯+𝑦)]π‘₯,π‘¦βˆˆπ”½2𝑛 is a Hadamard matrix (i.e. 𝐻×𝐻𝑑=2𝑛𝐼, where 𝐼 is the identity matrix),
  • the support of 𝑓 is a difference set of the elementary Abelian 2-group 𝔽2𝑛.

Bent functions are also called perfect nonlinear functions.

The dual of a bent 𝑓 function is also a bent function, where the dual is defined as

and its own dual is 𝑓 itself.

Bent functions and algebraic degree

  • For 𝑛 even and at least 4 the algebraic degree of any bent function is at most 𝑛/2.
  • The algebraic degree of a bent function and of its dual satisfy the following relation:
  • Obviously, no affine function can be bent.
  • When 𝑓 is quadratic, then it is affine equivalent to the function
  • The characterisation of cubic bent functions has been done for small dimensions (𝑛≀8).


The Maiorana-McFarland Construction

For 𝑛=2π‘š, 𝔽2𝑛={(π‘₯,𝑦) : π‘₯,π‘¦βˆˆπ”½2π‘š}, 𝑓 is of the form

where πœ‹ is a permutation of 𝔽2π‘š and 𝑔 is any π‘š-variable Boolean function. Any such function is bent (the bijectivity of πœ‹ is a necessary and sufficient condition). The dual function is .

Such construction contains, up to affine equivalence, all quadratic bent functions and all bent functions in at most 6 variables.