Bent function

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: {{defn| 2^{2-1} - 2^{\frac{2}{2}-1} = 2 - 1 = 1 }} 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 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: {{defn| 2^{2-1} - 2^{\frac{2}{2}-1} = 2 - 1 = 1 }} ]] 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. 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. 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). \hat{f}(a) = \sum_{\scriptstyle{x \in \Z_2^n}} (-1)^{f(x) + a \cdot x}, where is the dot product in Z . Alternatively, let and . Then and hence \hat{f}(a) = \left|S_0(a)\right| - \left|S_1(a)\right| = 2 \left|S_0(a)\right| - 2^n. For any Boolean function f and , the transform lies in the range -2^n \leq \hat{f}(a) \leq 2^n. Moreover, the linear function and the affine function correspond to the two extreme cases, since \hat{f}_0(a) = 2^n,~ \hat{f}_1(a) = -2^n. Thus, for each the value of \hat{f}(a) characterizes where the function f(x) lies in the range from f 0 (x) to f 1 (x). \hat{f}(a) = W\left(2^n\right) (-1)^{f(a)}, where W(2 n ) is the natural-ordered Walsh matrix and the sequence is treated as a column vector. Rothaus proved that bent functions exist only for even n, and that for a bent function f, \left|\hat{f}(a)\right| = 2^{n/2} for all . In fact, \hat{f}(a) = 2^{n/2}(-1)^{g(a)} , where g is also bent. In this case, \hat{g}(a) = 2^{n/2}(-1)^{f(a)} , so f and g are considered dual functions. Every bent function has a Hamming weight (number of times it takes the value 1) of , 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 , the maximum possible. Conversely, any Boolean function with nonlinearity is bent. The degree of f in algebraic normal form (called the nonlinear order of f) is at most (for ). Although bent functions are vanishingly rare among Boolean functions of many variables, they come in many different kinds. There has been detailed research into special classes of bent functions, such as the homogeneous ones or those arising from a monomial over a finite field, but so far the bent functions have defied all attempts at a complete enumeration or classification. If is a bent function on the elementary abelian group , then is a Hadamard matrix, and the support of (or its complement) is a Hadamard difference set in . This construction gives a Hadamard matrix developed over a noncyclic group; whether a real circulant (cyclic) Hadamard matrix of order greater than 4 can exist at all is the subject of Ryser's conjecture on circulant Hadamard matrices, a long-standing open problem in combinatorics. \hat{f}(a) = \sum_{x \in \mathbb{Z}_m^n} e^{\frac{2\pi i}{m} (f(x) - a \cdot x)} has constant absolute value m n/2 . Perfectly nonlinear functions f:\mathbb{Z}_m^n \to \mathbb{Z}_m , those such that for all nonzero a, takes on each value times, are generalized bent. If m is prime, the converse is true. In most cases only prime m are considered. For odd prime m, there are generalized bent functions for every positive n, even and odd. They have many of the same good cryptographic properties as the binary bent functions. Semi-bent functions are an odd-order counterpart to bent functions. A semi-bent function is f:\mathbb{Z}_m^n \to \mathbb{Z}_m with n odd, such that \left|\hat{f}\right| takes only the values 0 and m (n+1)/2 . They also have good cryptographic characteristics, and some of them are balanced, taking on all possible values equally often. The partially bent functions form a large class defined by a condition on the Walsh transform and autocorrelation functions. All affine and bent functions are partially bent. This is in turn a proper subclass of the plateaued functions. The idea behind the hyper-bent functions is to maximize the minimum distance to all Boolean functions coming from bijective monomials on the finite field GF(2 n ), not just the affine functions. 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 f:\Z_2^n \to \Z_2^n , such as almost bent functions and crooked functions. While not bent functions themselves (these are not even Boolean functions), they are closely related to the bent functions and have good nonlinearity properties.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368736978 under CC BY-SA 4.0; modifications have been made.