Bent function: Difference between revisions
imported>Andrey Khalyavin No edit summary |
mNo edit summary |
||
| (9 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
A '''bent function''' is a boolean function of <math>n</math> variables that | A '''bent function''' is a boolean function of <math>n</math> variables that has nonlinearity equal to <math>2^{n-1}-2^{n/2-1}</math>. The [[Walsh-Hadamard coefficients]] of a 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. The high [[non-linearity]] makes them useful in [[cryptography]], in the construction of [[stream cipher]]s or [[block cipher]]s. Bent functions are a specific case of [[plateaued function]]s. | ||
== Main properties == | == Main properties == | ||
One of the most | One of the most useful property distinguishing bent functions uses derivatives: | ||
:''A boolean function <math>f</math> is bent if and only if every derivative <math>D_uf(x)</math> is balanced for <math>u\neq0</math>. | :''A boolean function <math>f</math> is bent if and only if every derivative <math>D_uf(x)</math> is balanced for <math>u\neq0</math>. | ||
The minimal degree of bent function is <math>2</math> (the function <math>x_1x_2+x_3x_4+\cdots+x_{2n-1}x_{2n}</math> is bent), the maximal degree of bent function of <math>2n</math> variables is <math>n</math>. | The minimal degree of bent function is <math>2</math> (the function <math>x_1x_2+x_3x_4+\cdots+x_{2n-1}x_{2n}</math> is bent), the maximal degree of bent function of <math>2n</math> variables is <math>n</math>. | ||
The maximal dimension of linear space where a bent function of <math>2n</math> variables is constant also equals to <math>n</math>. A bent function which do have such linear space is called '''normal'''. Most constructions of bent functions give normal bent functions. | |||
== Transformations on bent functions == | |||
It has long been known that adding an [[affine function]] to a bent function gives another bent function. Harris and Adams <ref name="s-box"> {{cite paper | |||
| title = Key-Dependent S-Box Manipulations | |||
| author = Sandy Harris & Carlisle Adams | |||
| conference = selected Areas in Cryptography | |||
| year = 1998 | |||
| publisher = Springer-Verlag | |||
| url= http://www.springerlink.com/content/utpvr3g8xtclvn75/}}</ref> show that permuting the input bits or adding affine functions to one or more inputs also give bent output. | |||
== Dual bent function == | == Dual bent function == | ||
Signs of Walsh- | Signs of Walsh-Hadamard 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 series == | ||
== Bent function constructions == | == Bent function constructions == | ||
One paper is <ref name=generate>{{cite paper | author = C. Adams and S. Tavares | |||
| title = Generating and Counting Binary Bent Sequences | |||
| journal = IEEE Transactions on Information Theory, vol. 36, no. 5 | |||
| date = September, 1990 | |||
| pages = 1170-1173 }}</ref>. | |||
== Bent function enumeration == | == Bent function enumeration == | ||
For the number of bent function <math>B_{2n}</math> very little is know. <math>B_2=8, B_4=896, B_6=5\,425\,430\,528</math>. Because degree of bent function is bounded by <math>n</math> it is easy to show that <math>B_{2n}\le2^{2^{2n-1}+\frac{1}{2}{2n\choose n}}</math>. This result can be | For the number of bent function <math>B_{2n}</math> very little is know. <math>B_2=8, B_4=896, B_6=5\,425\,430\,528</math>. Because degree of bent function is bounded by <math>n</math> it is easy to show that <math>B_{2n}\le2^{2^{2n-1}+\frac{1}{2}{2n\choose n}}</math>. This result can be slightly improved but still remain very far from the truth. | ||
==References== | |||
{{reflist|2}}[[Category:Suggestion Bot Tag]] | |||
Latest revision as of 06:00, 18 July 2024
A bent function is a boolean function of variables that has nonlinearity equal to . The Walsh-Hadamard coefficients of a 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. The high non-linearity makes them useful in cryptography, in the construction of stream ciphers or block ciphers. Bent functions are a specific case of plateaued functions.
Main properties
One of the most useful 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 .
The maximal dimension of linear space where a bent function of variables is constant also equals to . A bent function which do have such linear space is called normal. Most constructions of bent functions give normal bent functions.
Transformations on bent functions
It has long been known that adding an affine function to a bent function gives another bent function. Harris and Adams [1] show that permuting the input bits or adding affine functions to one or more inputs also give bent output.
Dual bent function
Signs of Walsh-Hadamard 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
One paper is [2].
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 slightly improved but still remain very far from the truth.
References
- ↑ Sandy Harris & Carlisle Adams. Key-Dependent S-Box Manipulations. Springer-Verlag.
- ↑ C. Adams and S. Tavares (September, 1990). "Generating and Counting Binary Bent Sequences".