We are creating the world's most trusted encyclopedia and knowledge base.
Once you join us and log in, you'll be able to edit this page instantly!

Bent function

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

This is a draft article, under development. These unapproved articles are subject to a disclaimer.

[edit intro]

The Write-a-Thon is Wednesday, September 3rd!

A bent function is a boolean function of $n$ variables that have nonlinearity equal to $2 n - 1 - 2 n / 2 - 1$ . The Walsh-Adamar coefficients of a bent function are equal to $\pm 2^{n/2}$ ; this gives the alternative definition of bent functions. Bent functions have even number of variables, and achieve the bound of maximal possible nonlinearity. This makes them a good bases for cryptographic stream cyphers. Bent functions are a specific case of plateaued functions.

1 Main properties
2 Dual bent function
3 Bent function series
4 Bent function constructions
5 Bent function enumeration

Main properties

One of the most usefull property distinguishing bent functions uses derivatives:

A boolean function $f$ is bent if and only if every derivative $D u f (x)$ is balanced for $u\neq0$ .

The minimal degree of bent function is $2$ (the function $x_1x_2+x_3x_4+\cdots+x_{2n-1}x_{2n}$ is bent), the maximal degree of bent function of $2 n$ variables is $n$ .

The maximal dimension of linear space where a bent function of $2 n$ variables is constant also equals to $n$ . A bent function which do have such linear space is called normal. Most constructions of bent functions give normal bent functions.

Dual bent function

Signs of Walsh-Adamar coefficients can be transformed to another boolean function of the same number of variables. This function is also bent and is called dual bent function. The dual function to the dual function is the function itself.

Bent function series

Bent function constructions

Bent function enumeration

For the number of bent function $B 2 n$ very little is know. $B_2=8, B_4=896, B_6=5\,425\,430\,528$ . Because degree of bent function is bounded by $n$ it is easy to show that $B_{2n}\le2^{2^{2n-1}+\frac{1}{2}{2n\choose n}}$ . This result can be slighly improved but still remain very far from the truth.