Bent function

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.

[3] Bent functions are defined in terms of the Walsh transform.

The simplest examples of bent functions, written in algebraic normal form, are F(x1, x2) = x1x2 and G(x1, x2, x3, x4) = x1x2 ⊕ x3x4.

[6] Every bent function has a Hamming weight (number of times it takes the value 1) of 2n−1 ± 2n/2−1, and in fact agrees with any affine function at one of those two numbers of points.

So the nonlinearity of f (minimum number of times it equals any affine function) is 2n−1 − 2n/2−1, the maximum possible.

[4] The degree of f in algebraic normal form (called the nonlinear order of f) is at most ⁠n/2⁠ (for n > 2).

There has been detailed research into special classes of bent functions, such as the homogeneous ones[7] or those arising from a monomial over a finite field,[8] but so far the bent functions have defied all attempts at a complete enumeration or classification.

[2] As early as 1982 it was discovered that maximum length sequences based on bent functions have cross-correlation and autocorrelation properties rivalling those of the Gold codes and Kasami codes for use in CDMA.

The properties of bent functions are naturally of interest in modern digital cryptography, which seeks to obscure relationships between input and output.

By 1988 Forré recognized that the Walsh transform of a function can be used to show that it satisfies the strict avalanche criterion (SAC) and higher-order generalizations, and recommended this tool to select candidates for good S-boxes achieving near-perfect diffusion.

[10] Indeed, the functions satisfying the SAC to the highest possible order are always bent.

[11] Furthermore, the bent functions are as far as possible from having what are called linear structures, nonzero vectors a such that f(x + a) + f(x) is a constant.

In the language of differential cryptanalysis (introduced after this property was discovered) the derivative of a bent function f at every nonzero point a (that is, fa(x) = f(x + a) + f(x)) is a balanced Boolean function, taking on each value exactly half of the time.

[5] Given such good diffusion properties, apparently perfect resistance to differential cryptanalysis, and resistance by definition to linear cryptanalysis, bent functions might at first seem the ideal choice for secure cryptographic functions such as S-boxes.

In particular, an invertible S-box cannot be constructed directly from bent functions, and a stream cipher using a bent combining function is vulnerable to a correlation attack.

Instead, one might start with a bent function and randomly complement appropriate values until the result is balanced.

[5] But functions produced in this way may lose other desirable properties, even failing to satisfy the SAC – so careful testing is necessary.

[12][13][14] Some of this theoretical research has been incorporated into real cryptographic algorithms.

The CAST design procedure, used by Carlisle Adams and Stafford Tavares to construct the S-boxes for the block ciphers CAST-128 and CAST-256, makes use of bent functions.

The most common class of generalized bent functions is the mod m type,

, those such that for all nonzero a, f(x + a) − f(a) takes on each value mn−1 times, are generalized bent.

They have many of the same good cryptographic properties as the binary bent functions.

They also have good cryptographic characteristics, and some of them are balanced, taking on all possible values equally often.

For these functions this distance is constant, which may make them resistant to an interpolation attack.

Other related names have been given to cryptographically important classes of functions