Citizendium - building a quality free general knowledge encyclopedia. Click here to join and contribute—free
Many thanks December donors; special to Darren Duncan. January donations open; need minimum total $100. Let's exceed that.

Donate here. By donating you gift yourself and CZ.


Bent function

From Citizendium, the Citizens' Compendium

Jump to: navigation, search
This article is a stub and thus not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.

A bent function is a boolean function of n variables that has nonlinearity equal to 2^{n-1}-2^{n/2-1}. The Walsh-Hadamard 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. 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.

Contents

Main properties

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

A boolean function f is bent if and only if every derivative D_uf(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 2n variables is n.

The maximal dimension of linear space where a bent function of 2n 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.

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 B_{2n} 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 slightly improved but still remain very far from the truth.

References

  1. Sandy Harris & Carlisle Adams. Key-Dependent S-Box Manipulations. Springer-Verlag.
  2. C. Adams and S. Tavares (September, 1990). "Generating and Counting Binary Bent Sequences".
Views
Personal tools