Bent function: Difference between revisions
imported>Andrey Khalyavin |
imported>Andrey Khalyavin No edit summary |
||
Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
A '''bent function''' is a boolean function of <math>n</math> variables that have nonlinearity equal to <math>2^{n-1}-2^{n/2-1}</math>. [[Walsh-Adamar coefficients]] of bent function are equal to <math>\pm 2^{n/2}</math>. This gives the alternative definition of bent functions. Bent functions have even number of variables and | A '''bent function''' is a boolean function of <math>n</math> variables that have nonlinearity equal to <math>2^{n-1}-2^{n/2-1}</math>. [[Walsh-Adamar coefficients]] of bent function are equal to <math>\pm 2^{n/2}</math>. 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 blocks for cryptographics stream cyphers. Bent functions is a specific case of [[plateaued function]]s. | ||
== Main properties == | == Main properties == |
Revision as of 04:15, 13 April 2008
A bent function is a boolean function of variables that have nonlinearity equal to . Walsh-Adamar coefficients of bent function are equal to . 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 blocks for cryptographics stream cyphers. Bent functions is a specific case of plateaued functions.
Main properties
One of the most usefull property distinguishing bent functions uses derivatives:
- A boolean function is bent if and only if every derivative is balanced for .
The minimal degree of bent function is (the function is bent), the maximal degree of bent function of variables is .
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 very little is know. . Because degree of bent function is bounded by it is easy to show that . This result can be slighly improved but still remain very far from the truth.