Hubbry Logo
search
logo
Bent function avatar
Bent function
Bent function
current hub
1043284

Bent function

logo
Community Hub0 Subscribers
Read side by side
Bent function
View on Wikipedia
from Wikipedia
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]

Walsh transform

[edit]

Bent functions are defined in terms of the Walsh transform. The Walsh transform of a Boolean function is the function given by

where a · x = a1x1 + a2x2 + … + anxn (mod 2) is the dot product in Zn
2.[4] Alternatively, let S0(a) = { x ∈ Zn
2 : f(x) = a · x } and S1(a) = { x ∈ Zn
2 : f(x) ≠ a · x }. Then |S0(a)| + |S1(a)| = 2n and hence

For any Boolean function f and a ∈ Zn
2, the transform lies in the range

Moreover, the linear function f0(x) = a · x and the affine function f1(x) = a · x + 1 correspond to the two extreme cases, since

Thus, for each a ∈ Zn
2 the value of characterizes where the function f(x) lies in the range from f0(x) to f1(x).

Definition and properties

[edit]

Rothaus defined a bent function as a Boolean function whose Walsh transform has constant absolute value. Bent functions are in a sense equidistant from all the affine functions, so they are equally hard to approximate with any affine function.

The simplest examples of bent functions, written in algebraic normal form, are F(x1, x2) = x1x2 and G(x1, x2, x3, x4) = x1x2 ⊕ x3x4. This pattern continues: x1x2 ⊕ x3x4 ⊕ … ⊕ xn−1xn is a bent function for every even n, but there is a wide variety of other bent functions as n increases.[5] The sequence of values (−1)f(x), with x ∈ Zn
2 taken in lexicographical order, is called a bent sequence; bent functions and bent sequences have equivalent properties. In this ±1 form, the Walsh transform is easily computed as

where W(2n) is the natural-ordered Walsh matrix and the sequence is treated as a column vector.[6]

Rothaus proved that bent functions exist only for even n, and that for a bent function f, for all a ∈ Zn
2.[4] In fact, , where g is also bent. In this case, , so f and g are considered dual functions.[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. Conversely, any Boolean function with nonlinearity 2n−1 − 2n/2−1 is bent.[4] The degree of f in algebraic normal form (called the nonlinear order of f) is at most ⁠n/2⁠ (for n > 2).[5]

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[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.

Constructions

[edit]

There are several types of constructions for bent functions.[2]

  • Combinatorial constructions: iterative constructions, Maiorana–McFarland construction, partial spreads, Dillon's and Dobbertin's bent functions, minterm bent functions, bent iterative functions
  • Algebraic constructions: monomial bent functions with exponents of Gold, Dillon, Kasami, Canteaut–Leander and Canteaut–Charpin–Kuyreghyan; Niho bent functions, etc.

Applications

[edit]

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.[9] These sequences have several applications in spread spectrum techniques.

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. This property is called perfect nonlinearity.[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. Their fatal flaw is that they fail to be balanced. 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. The modified function still has high nonlinearity, and as such functions are very rare the process should be much faster than a brute-force search.[5] But functions produced in this way may lose other desirable properties, even failing to satisfy the SAC – so careful testing is necessary.[11] A number of cryptographers have worked on techniques for generating balanced functions that preserve as many of the good cryptographic qualities of bent functions as possible.[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.[14] The cryptographic hash function HAVAL uses Boolean functions built from representatives of all four of the equivalence classes of bent functions on six variables.[15] The stream cipher Grain uses an NLFSR whose nonlinear feedback polynomial is, by design, the sum of a bent function and a linear function.[16]

Generalizations

[edit]

More than 25 different generalizations of bent functions are described in Tokareva's 2015 monograph.[2] There are algebraic generalizations (q-valued bent functions, p-ary bent functions, bent functions over a finite field, generalized Boolean bent functions of Schmidt, bent functions from a finite Abelian group into the set of complex numbers on the unit circle, bent functions from a finite Abelian group into a finite Abelian group, non-Abelian bent functions, vectorial G-bent functions, multidimensional bent functions on a finite Abelian group), combinatorial generalizations (symmetric bent functions, homogeneous bent functions, rotation symmetric bent functions, normal bent functions, self-dual and anti-self-dual bent functions, partially defined bent functions, plateaued functions, Z-bent functions and quantum bent functions) and cryptographic generalizations (semi-bent functions, balanced bent functions, partially bent functions, hyper-bent functions, bent functions of higher order, k-bent functions).

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

has constant absolute value mn/2. Perfect nonlinear functions , those such that for all nonzero a, f(x + a) − f(a) takes on each value mn−1 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.[17][18]

Semi-bent functions are an odd-order counterpart to bent functions. A semi-bent function is with n odd, such that 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.[19]

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.[20]

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(2n), 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 , 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.

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Bent function

View on Grokipedia
from Grokipedia
Bent functions are a class of balanced Boolean functions mapping from {0,1}n\{0,1\}^n to {0,1}\{0,1\} that achieve the maximum possible nonlinearity for even-dimensional inputs, characterized by a flat Walsh-Hadamard transform spectrum where all coefficients have absolute value 2n/22^{n/2}.[1][2] First introduced by Oscar Rothaus in 1976, these functions were later popularized in cryptographic contexts due to their resistance to linear cryptanalysis and other attacks, with early studies by John Dillon in the 1970s highlighting their construction methods.[3][4] Primarily defined and studied for even nn, bent functions exhibit optimal properties such as high algebraic degree at most n/2n/2, making them ideal for designing secure symmetric ciphers and error-correcting codes.[5] Their balanced nature ensures an equal number of inputs mapping to 0 and 1, while the maximal nonlinearity distinguishes them from other Boolean functions by minimizing correlations with linear approximations.[6] Applications extend to symmetric cryptography, where bent functions serve as building blocks for S-boxes, and to coding theory for sequences with ideal autocorrelation properties.[7][8] Research on bent functions has evolved to include generalizations like partially bent and hyper-bent functions, with ongoing constructions using algebraic techniques such as cyclic codes and Dillon-like methods to generate new families resistant to advanced attacks.[2][9] Despite their even-dimensional restriction, bent functions remain a cornerstone of discrete mathematics and computer science, influencing fields beyond cryptography like signal processing and combinatorial designs.[1]

Introduction and Definition

Definition

A bent function is a special class of Boolean functions defined over the finite field $ \mathbb{F}_2^n $, mapping from $ n $-dimensional binary vectors to a single binary output. Formally, a function $ f: \mathbb{F}_2^n \to \mathbb{F}_2 $ is called bent if the absolute values of its Walsh-Hadamard transform are constantly equal to $ 2^{n/2} $ for all $ a \in \mathbb{F}_2^n $. This definition requires that $ n $ be even, as bent functions do not exist for odd dimensions due to the impossibility of achieving the required flat spectrum in the Walsh transform under those conditions. Bent functions achieve maximal nonlinearity, measuring how far a function deviates from being linear, at the highest possible level for their dimension. For a concrete illustration, the simplest bent function occurs when $ n=2 $, given by $ f(x_1, x_2) = x_1 x_2 $, which satisfies the Walsh transform condition.

Fundamental Properties

Bent functions exhibit a characteristic two-level autocorrelation spectrum, where the autocorrelation function $ C_f(a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + f(x+a)} $ equals $ 2^n $ when $ a = 0 $ and 0 otherwise for all $ a \in \mathbb{F}_2^n $.[2] This property arises directly from the flat Walsh-Hadamard transform of bent functions and ensures that their first-order differences (derivatives) $ D_a f(x) = f(x) + f(x+a) $ are balanced Boolean functions for every nonzero $ a $, meaning each derivative takes the values 0 and 1 equally often across the input space.[2] A key aspect of bent functions is their duality: for a bent function $ f: \mathbb{F}_2^n \to \mathbb{F}_2 $, the dual function $ \hat{f} $ is defined such that $ (-1)^{\hat{f}(u)} = 2^{-n/2} W_f(u) $ for all $ u \in \mathbb{F}_2^n $, where $ W_f $ denotes the Walsh-Hadamard transform of $ f $.[10] This dual $ \hat{f} $ is itself a bent function, establishing that bent functions occur in pairs, and the construction via the inverse Walsh transform preserves the maximal nonlinearity property.[10] The duality relation highlights the symmetry in the spectral properties of bent functions and facilitates analysis in cryptographic applications.[2] Bent functions are equivalent to perfect nonlinear functions in the scalar case over $ \mathbb{F}_2 $, where a function is perfectly nonlinear if all its nonzero derivatives are balanced, a condition that precisely matches the definition of bentness for even-dimensional inputs.[11] This equivalence extends to more general p-ary settings under natural parameter restrictions, such as for c-differential bent functions and perfect c-nonlinear functions, where the former's flat generalized Walsh spectrum implies the latter's uniform distribution of c-derivatives.[11] Such relations underscore the role of bent functions in achieving optimal resistance to differential attacks in cryptography.[11]

History and Development

Discovery and Early Work

Bent functions were first introduced by Oskar Rothaus in an unpublished manuscript around the mid-1960s, with the work formally appearing in print in 1976 under the title "On 'bent' functions."[5][12] This seminal paper defined bent functions as balanced Boolean functions achieving maximal nonlinearity, characterized by a flat Walsh-Hadamard transform spectrum, and explored their properties in even dimensions.[13] The early motivations for studying bent functions stemmed from applications in coding theory and sequence design, where their maximal nonlinearity properties made them ideal for constructing sequences with optimal autocorrelation characteristics.[1] These functions were particularly linked to Hadamard matrices, as the existence of bent functions in dimension n implies the existence of Hadamard matrices of order 2^n, providing a combinatorial tool for matrix constructions relevant to error-correcting codes and experimental designs.[1][14] The first explicit mention of bent functions beyond Rothaus's work appeared in 1974 by John F. Dillon in his PhD thesis, who discussed them in the context of difference families and partial spreads within finite fields, highlighting their role in generating difference sets with desirable combinatorial properties.[14] Dillon's contributions built on Rothaus's foundations, emphasizing connections to multiplicative characters and singer difference sets in projective geometries.[14]

Key Milestones and Researchers

Bent functions gained significant attention in the cryptographic community following their popularization by W. Meier and O. Staffelbach in 1989, who highlighted their maximal nonlinearity as ideal for designing secure S-boxes in block ciphers. Their work emphasized the flat Walsh-Hadamard spectrum of bent functions, establishing a connection to correlation immune functions and paving the way for their use in resisting linear cryptanalysis. In the 1990s, Kaisa Nyberg made key contributions by introducing the concept of perfect nonlinear functions in 1994, demonstrating that such functions over finite fields are inherently bent when viewed as Boolean functions, thus bridging algebraic and Boolean perspectives in cryptography. Nyberg's analysis extended to mappings between vector spaces, showing that bent functions achieve optimal resistance to linear attacks, which influenced the design of ciphers like the Advanced Encryption Standard (AES).

Mathematical Properties

Nonlinearity and Walsh Spectrum

Bent functions achieve the maximum possible nonlinearity among all Boolean functions from {0,1}n\{0,1\}^n to {0,1}\{0,1\} for even nn, where the nonlinearity NfN_f is defined as the minimum Hamming distance to any affine function and equals Nf=2n−1−2n/2−1N_f = 2^{n-1} - 2^{n/2 - 1}.[2] This maximal value distinguishes bent functions from other nonlinear Boolean functions, as it represents the highest attainable resistance to linear approximations in cryptographic contexts.[15] The Walsh-Hadamard transform provides a key spectral characterization of bent functions, defined for a function ff as
Wf(a)=∑x∈{0,1}n(−1)f(x)+⟨a,x⟩ W_f(a) = \sum_{x \in \{0,1\}^n} (-1)^{f(x) + \langle a, x \rangle}
for each a∈{0,1}na \in \{0,1\}^n, where ⟨a,x⟩\langle a, x \rangle denotes the dot product modulo 2.[16] For bent functions, the absolute value of the Walsh transform is constant across all aa, specifically ∣Wf(a)∣=2n/2|W_f(a)| = 2^{n/2} for every aa, resulting in a flat spectrum that underscores their perfect nonlinearity.[17] This flatness implies that no linear approximation correlates strongly with the function, enhancing its suitability for cryptographic primitives.[18] In cryptography, the maximal nonlinearity and flat Walsh spectrum of bent functions provide strong resistance to linear cryptanalysis, where attackers seek high-correlation linear approximations to exploit the function's behavior.[14] For instance, this property ensures that the bias in any linear approximation is minimized to 2−n/22^{-n/2}, making attacks computationally infeasible for large even nn.[8]

Algebraic Degree and Bounds

The algebraic degree $ d(f) $ of a Boolean function $ f: \mathbb{F}_2^n \to \mathbb{F}_2 $ is defined as the highest degree of any monomial with a nonzero coefficient in its algebraic normal form (ANF), which represents $ f $ as a multivariate polynomial over $ \mathbb{F}_2 $.[19] For bent functions, which exist only when $ n $ is even, the algebraic degree is bounded above by $ n/2 $, establishing the theoretical maximum possible degree for such functions.[20][19] In the specific case of $ n=8 $, this bound implies a maximum degree of 4, which is achievable; for instance, certain constructions yield bent functions of degree exactly 4.[19][21] Maiorana-McFarland constructions, a primary method for generating bent functions via $ f(x,y) = x \cdot \pi(y) \oplus g(y) $ where $ \pi $ is a permutation on $ \mathbb{F}_2^{n/2} $ and $ g $ is a Boolean function, can produce bent functions of this maximal degree 4 for $ n=8 $, depending on the choices of $ \pi $ and $ g $.[19]

Construction Techniques

Basic Constructions

One of the simplest methods to construct bent functions in higher even dimensions is the direct sum construction, which combines bent functions from smaller dimensions. Specifically, if f:F2m→F2f: \mathbb{F}_2^m \to \mathbb{F}_2 and g:F2n→F2g: \mathbb{F}_2^n \to \mathbb{F}_2 are bent functions with m+nm + n even, then the direct sum h(u,v)=f(u)+g(v)h(u, v) = f(u) + g(v) for u∈F2mu \in \mathbb{F}_2^m and v∈F2nv \in \mathbb{F}_2^n is a bent function on F2m+n\mathbb{F}_2^{m+n}.[22] This construction preserves the bent property because the Walsh transform of hh is the product of the Walsh transforms of ff and gg, resulting in a flat spectrum of magnitude 2(m+n)/22^{(m+n)/2}.[22] Another elementary construction is the Maiorana-McFarland method, which produces bent functions of algebraic degree 2 in even dimensions n=2mn = 2m. For x∈F2mx \in \mathbb{F}_2^m and y∈F2my \in \mathbb{F}_2^m, the function is defined as f(x,y)=⟨x,ϕ(y)⟩+g(y)f(x, y) = \langle x, \phi(y) \rangle + g(y), where ϕ:F2m→F2m\phi: \mathbb{F}_2^m \to \mathbb{F}_2^m is a permutation (or more generally, such that for every a∈F2ma \in \mathbb{F}_2^m, the preimage ϕ−1(a)\phi^{-1}(a) is an affine hyperplane of dimension m−1m-1), and g:F2m→F2g: \mathbb{F}_2^m \to \mathbb{F}_2 is an arbitrary Boolean function.[23] The bent property arises because this form ensures the Walsh coefficients take values ±2n/2\pm 2^{n/2} exactly.[23] A basic choice for ϕ\phi is the identity permutation, yielding quadratic bent functions useful for small nn. For illustration in dimension n=4n=4, a quadratic bent function can be given explicitly in algebraic normal form (ANF), up to equivalence and linear terms, with quadratic part f(x1,x2,x3,x4)=x1x2⊕x1x3⊕l(x1,x2,x3,x4)f(x_1, x_2, x_3, x_4) = x_1 x_2 \oplus x_1 x_3 \oplus l(x_1, x_2, x_3, x_4), where ll is an appropriate affine function to ensure balance.[24] This function achieves the maximal nonlinearity of 6 and has Walsh spectrum values of ±4\pm 4, confirming its bent nature, and serves as a concrete example obtainable via the Maiorana-McFarland construction with appropriate ϕ\phi and gg.[24]

Advanced and Generalized Constructions

Dillon's partial spread construction provides a method for generating bent functions by considering a partial spread of subspaces in the finite field F2n\mathbb{F}_{2^n}, where n=2mn = 2m is even. Specifically, it involves selecting 2m−12^{m-1} or 2m−1+12^{m-1} + 1 disjoint mm-dimensional subspaces whose union, when identified with the vector space F2n\mathbb{F}_{2^n}, covers a significant portion of the space, and defining the bent function as the sum of indicator functions of these subspaces.[25] This construction leverages trace functions over finite fields to represent the bent function in a bivariate form, such as f(x,y)=Trm1(y+xG(yx2m−2))f(x, y) = \mathrm{Tr}_m^1(y + x G(y x^{2^m - 2})) for x,y∈F2mx, y \in \mathbb{F}_{2^m}, where GG is a suitable polynomial ensuring the function's bentness through properties like permutations and two-to-one mappings.[25] The resulting functions belong to Dillon's Class H (or its extension H\mathcal{H}), exhibit linear restrictions on subspaces of the form uF2mu \mathbb{F}_{2^m} for u∈F2n∗u \in \mathbb{F}_{2^n}^*, and achieve the maximal nonlinearity of 2n−1−2m−12^{n-1} - 2^{m-1}.[25] Carlet's construction builds on Niho exponents to produce bent functions of higher algebraic degrees for n=2mn = 2m. It defines functions in bivariate form as g(x,y)={Trm1(xH(yx))if x≠0Trm1(μy)if x=0g(x, y) = \begin{cases} \mathrm{Tr}_m^1(x H(y x)) & \text{if } x \neq 0 \\ \mathrm{Tr}_m^1(\mu y) & \text{if } x = 0 \end{cases}, where H:F2m→F2mH: \mathbb{F}_{2^m} \to \mathbb{F}_{2^m} and μ∈F2m\mu \in \mathbb{F}_{2^m}, with bentness ensured if G(z)=H(z)+μzG(z) = H(z) + \mu z is a permutation and z↦G(z)+βzz \mapsto G(z) + \beta z is two-to-one for every β∈F2m∗\beta \in \mathbb{F}_{2^m}^*.[25] By associating these with o-polynomials—permutation polynomials where z↦G(z+γ)+G(γ)zz \mapsto \frac{G(z + \gamma) + G(\gamma)}{z} (for z≠0z \neq 0) is a permutation for every γ\gamma—Carlet constructs eight new infinite classes of such bent functions, some with degrees up to m+32\frac{m+3}{2} for odd m>3m > 3, surpassing those of standard Niho bent functions.[25] These functions, often not affine equivalent to those in the Maiorana-McFarland class, maintain optimal nonlinearity and are represented univariately via Niho power functions like Trm1(at2m+1)\mathrm{Tr}_m^1(a t^{2^m + 1}).[25] Generalizations to vectorial bent functions extend the scalar case to mappings F:F2n→F2rF: \mathbb{F}_{2^n} \to \mathbb{F}_{2^r} (with rr even), where FF is bent if every component function fa(x)=Tr1(aF(x))f_a(x) = \mathrm{Tr}_1(a F(x)) for a∈F2r∗a \in \mathbb{F}_{2^r}^* is bent.[2] Bent criteria for vectorial functions include the requirement that the Walsh-Hadamard transform of each component achieves absolute values of 2n/22^{n/2}, or equivalently, that differences F(x+y)+F(x)F(x + y) + F(x) are balanced for all nonzero yy.[2] Constructions often analogize the Maiorana-McFarland approach, such as F(x′,x′′)=(x′,h(x′′))F(x', x'') = (x', h(x'')) where hh is a permutation, yielding vectorial bent functions with high nonlinearity; further generalizations include q-valued bent functions over Zqn\mathbb{Z}_q^n where the Walsh transform has flat spectrum of magnitude qn/2q^{n/2}.[2] These vectorial extensions are crucial for multi-output cryptographic primitives, preserving maximal distance from linear functions across components.[2]

Applications

In Cryptography

Bent functions play a crucial role in the design of substitution boxes (S-boxes) for block ciphers, providing optimal resistance to linear cryptanalysis due to their maximal nonlinearity, which ensures that the Walsh spectrum is flat and minimizes correlations with linear approximations.[26] This property makes them ideal for constructing S-boxes that achieve the highest possible nonlinearity, thereby enhancing security against attacks that exploit linear relations between input and output bits.[27] For instance, vectorial bent functions, also known as perfect nonlinear functions, offer the strongest resistance to differential cryptanalysis by ensuring that each output bit is a bent function of any nonzero linear combination of input bits, resulting in a differential uniformity of 2.[28] In stream ciphers, bent functions are applied in filter generators, where a linear feedback shift register (LFSR) sequence is passed through a nonlinear Boolean function to produce the keystream; their high nonlinearity helps resist correlation attacks by making it difficult for adversaries to correlate the output with the LFSR state.[29] Although bent functions are not balanced, modifications or related constructions like semi-bent functions are often used to leverage their nonlinearity while addressing balance issues in such generators.[30] This application underscores their value in symmetric cryptography for generating pseudorandom sequences with strong statistical properties against linear approximations.[3] A specific example of bent functions in block cipher design is found in the SAFER cipher family, where the core nonlinear transformation employs a perfect nonlinear function equivalent to a vectorial bent mapping, such as $ f(x) = 45^x \mod 257 $, to achieve optimal diffusion and resistance to both differential and linear attacks.[28] This design choice in SAFER K-64 and related variants demonstrates how bent-based S-boxes contribute to the cipher's security profile by maximizing nonlinearity in even-dimensional spaces.[31]

In Coding Theory and Signal Processing

Bent functions play a significant role in coding theory through their connections to Reed-Muller codes, where they help determine the covering radius and enhance code performance metrics. Specifically, the covering radius of the first-order Reed-Muller code RM(1,n) for even n is linked to the existence of bent functions, as these functions achieve the maximal possible Hamming distance from the set of affine functions, providing bounds on error-correcting capabilities in binary codes.[3] Extensions involving bent indicators allow for the construction of nonlinear codes that inherit favorable distance properties from their bent components, improving upon linear Reed-Muller structures in certain dimensions.[32] In spread-spectrum communication systems, bent sequences constructed from bent functions are utilized for code-division multiple-access (CDMA) due to their superior correlation properties. These sequences form families of nonlinear binary signals that attain Welch's lower bound on simultaneous autocorrelation and cross-correlation, enabling efficient user separation and reduced interference in multi-user environments.[33] The ideal two-level autocorrelation of bent sequences, stemming from the flat Walsh-Hadamard spectrum of bent functions, ensures minimal out-of-phase values, which is essential for synchronization and signal detection in CDMA systems.[34] Bent sequences also find applications in radar and sonar systems, where their low autocorrelation sidelobes facilitate high-resolution target detection by suppressing false returns and ambiguity peaks. This property arises from the bent functions' maximal nonlinearity, yielding sequences with near-ideal periodic autocorrelation suitable for pulse compression techniques in active sensing.[35]

Open Problems and Extensions

Known Challenges

One of the primary open problems in the study of bent functions is the complete classification of these functions up to affine equivalence for dimensions n > 6, which remains infeasible due to the exponential growth in their number as n increases. For instance, while exact counts are known for smaller even dimensions, such as 8 bent functions for n=2 and 896 for n=4, and even for n=8 the total count is known, the sheer volume for n ≥ 8 defies determination of equivalence classes under the general affine group. This exponential complexity arises from the combinatorial explosion inherent in Boolean function spaces, making systematic classification a persistent challenge in the field.[36][3][37] A significant challenge lies in constructing or identifying bent functions with prescribed properties, such as specific dual functions or minimal Hamming weight, which are crucial for tailored applications in cryptography and coding theory. Efforts to find bent functions whose duals satisfy particular conditions, like the dual bent property, often require innovative composition methods, yet many such instances remain elusive or computationally intensive to verify. Similarly, locating bent functions of minimal weight—representing the sparsest possible output distributions—poses difficulties, as these properties intersect with open questions on normality and spectral behavior, limiting the ability to meet exact specifications without resorting to ad hoc searches.[38][39] Computational limits further exacerbate these issues, particularly for n=8, where enumeration reveals exactly 99,270,589,263,970,357,858,612,428,80 bent functions (approximately 21062^{106}), rendering detailed analysis and property extraction highly complex despite the known total count. This scale underscores the practical barriers to exploring the full landscape of bent functions, even in moderate dimensions, and highlights the need for more efficient algorithmic approaches to handle the underlying exponential growth.[37]

Related Function Classes

Bent functions, which achieve maximal nonlinearity in even dimensions, have inspired several related classes of Boolean functions that extend or generalize their properties in various contexts. One prominent subclass is hyperbent functions, introduced by Youssef and Gong in 2001, which are bent functions over F2n\mathbb{F}_{2^n} that additionally exhibit a flat Fourier spectrum in the extended domain, satisfying cyclotomic equivalence conditions that enhance their cryptographic resilience against certain attacks.[40] These functions are particularly valued for their ability to maintain high nonlinearity while possessing a more uniform spectral distribution compared to standard bent functions. For odd dimensions nn, where bent functions do not exist due to the impossibility of achieving perfect balance and maximal nonlinearity simultaneously, semi-bent functions serve as a natural analogue, attaining nonlinearity close to the maximum possible value of 2n−1−2(n−1)/22^{n-1} - 2^{(n-1)/2}. Defined as functions whose Walsh transform takes values in {−2(n+1)/2,0,2(n+1)/2}\{-2^{(n+1)/2}, 0, 2^{(n+1)/2}\}, semi-bent functions balance the trade-offs inherent in odd-length inputs and are studied for their applications in sequence design and error-correcting codes. Another closely related class is almost perfect nonlinear (APN) functions, which differ from bent functions primarily in their domain applicability and spectral properties: while bent functions are defined for even nn and achieve a flat Walsh spectrum of absolute value 2n/22^{n/2}, APN functions operate effectively in both even and odd dimensions but only guarantee a differential uniformity of 2, meaning the difference distribution table has at most two solutions per entry, thus providing resistance to differential cryptanalysis without the full nonlinearity of bent functions. This distinction highlights how APN functions prioritize differential over linear approximation resistance, making them complementary to bent functions in cryptographic designs for odd-dimensional spaces.

References

  1. Bent Functions: Results and Applications to Cryptography
  2. [PDF] Generalizations of Bent Functions. A Survey 1
  3. [PDF] Bent and Plateaued Functions for Symmetric Cryptography
  4. A further study on the construction methods of bent functions and ...
  5. [PDF] Bent functions: fundamentals and results
  6. [PDF] New characterizations and construction methods of bent and hyper ...
  7. Constructions of 2-rotation symmetric bent functions based on ...
  8. A note on generalization of bent boolean functions
  9. Relations between Different Constructions of Bent Functions and ...
  10. [PDF] Bent and Semi-bent Functions via Linear Translators
  11. No Title
  12. Bent Functions: Results and Applications to Cryptography [1&nbsp
  13. (Open Access) On “bent” functions (1976) | O.S Rothaus - SciSpace
  14. [PDF] Bent functions and their connections to coding theory and ...
  15. More DD difference sets | Semantic Scholar
  16. ON DILLON'S CLASS H OF BENT FUNCTIONS, NIHO BENT ...
  17. [PDF] On Boolean functions which are bent and negabent
  18. [PDF] Calculating Nonlinearity of Boolean Functions with Walsh ...
  19. [PDF] Nega–Hadamard Transform, Bent and Negabent Functions - DTIC
  20. New characterizations and construction methods of bent and hyper ...
  21. [PDF] Bent Functions from Cellular Automata - Cryptology ePrint Archive
  22. Full article: Nearly bent functions - Taylor & Francis Online
  23. [PDF] Construction of rotation symmetric bent functions with maximum ...
  24. [PDF] A construction of bent functions from plateaued functions - HAL-Inria
  25. [PDF] Bent functions using Maiorana-McFarland secondary construction
  26. [PDF] Algebraic normal form of a bent function: properties and restrictions
  27. [PDF] Cryptographer's Toolkit for Construction of 8-Bit Bent Functions
  28. [PDF] The design of S-Boxes
  29. [PDF] ``Provable'' Security Against Differential and Linear Cryptanalysis
  30. [PDF] Design and Cryptanalysis of Stream Ciphers
  31. [PDF] Designing resilient functions and bent function for stream ciphers
  32. [PDF] CRYPTOGRAPHIC PROPERTIES OF BOOLEAN FUNCTIONS AND ...
  33. [1912.10811] On metric regularity of Reed-Muller codes - arXiv
  34. Bent-function sequences | IEEE Transactions on Information Theory
  35. Fast Generation of Bent Sequence Family - Science Alert
  36. [PDF] Algebraic Shift Register Sequences - Institute for Advanced Study
  37. [PDF] on constructions and enumeration of bent and semi-bent functions
  38. Bent functions satisfying the dual bent condition and permutations ...
  39. Note On two open problems on the normality of bent functions
  40. Counting all bent functions in dimension eight ... - ResearchGate
User Avatar
No comments yet.