Bent function

The four 2-ary Boolean functions with Hamming weight 1 are bent; i.e., their nonlinearity is 1 (these Hadamard matrices show the Hamming distance to each of the eight linear and affine functions).
The following formula shows that a 2-ary function is bent when its nonlinearity is 1:
The Boolean function is bent; i.e., its nonlinearity is 6 (which is what these Hadamard Matrices show).
The following formula shows that a 4-ary function is bent when its nonlinearity is 6:

In the mathematical field of combinatorics, a bent function is a Boolean function that is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance between truth tables. Concretely, this means the maximum correlation between the output of the function and a linear function is minimal. In addition, the derivatives of a bent function are balanced Boolean functions, so for any change in the input variables there is a 50 percent chance that the output value will change.

The maximal nonlinearity means approximating a bent function by an affine (linear) function is hard, a useful property in the defence against linear cryptanalysis. In addition, detecting a change in the output of the function yields no information about what change occurred in the inputs, making the function immune to differential cryptanalysis.

Bent functions were defined and named in the 1960s by Oscar Rothaus in research not published until 1976.[1] They have been extensively studied for their applications in cryptography, but have also been applied to spread spectrum, coding theory, and combinatorial design. The definition can be extended in several ways, leading to different classes of generalized bent functions that share many of the useful properties of the original.

It is known that V. A. Eliseev and O. P. Stepchenkov studied bent functions, which they called minimal functions, in the USSR in 1962.[2] However, their results have still not been declassified.

Bent functions are also known as perfectly nonlinear (PN) Boolean functions. Certain functions that are as close as possible to perfect nonlinearity (e.g. for functions of an odd number of bits, or vectorial functions) are known as almost perfectly nonlinear (APN).[3]

  1. ^ Cite error: The named reference rothaus was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference bent-book was invoked but never defined (see the help page).
  3. ^ Blondeau; Nyberg (2015-03-01). "Perfect nonlinear functions and cryptography". Finite Fields and Their Applications. 32: 120–147. doi:10.1016/j.ffa.2014.10.007. ISSN 1071-5797.