Bent function

The 2-ary bent functions with Hamming weight 1

Their nonlinearity is
$2^{2-1} - 2^{\frac{2}{2}-1} = 2-1 = 1$

The nonlinearity of the bent function $x_1 x_2~+~x_3 x_4$ is
$2^{4-1} - 2^{\frac{4}{2}-1} = 8-2 = 6$

$~+~$ stands for the exclusive or
(compare algebraic normal form)

In the mathematical field of combinatorics, a bent function is a special type of Boolean function. Defined and named in the 1960s by Oscar Rothaus in research not published until 1976, bent functions are so called because they are as different as possible from all linear and affine functions. 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.

Walsh transform

Bent functions are defined in terms of the Walsh transform. The Walsh transform of a Boolean function ƒ: Zn
2 → Z₂ is the function $\hat{f}:\Z_2^n \to \Z$ given by

$\hat{f}(a) = \sum_{\scriptstyle{x \in \Z_2^n}} (-1)^{f(x) + a \cdot x}$

where a · x = a₁x₁ + a₂x₂ + … + a_nx_n (mod 2) is the dot product in Zn
2.^[1] Alternatively, let S₀(a) = { x ∈ Zn
2 : ƒ(x) = a · x } and S₁(a) = { x ∈ Zn
2 : ƒ(x) ≠ a · x }. Then |S₀(a)| + |S₁(a)| = 2ⁿ and hence

$\hat{f}(a) = |S_0(a)| - |S_1(a)| = 2 |S_0(a)| - 2^n.$

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

$-2^n \leq \hat{f}(a) \leq 2^n.$

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

$\hat{f}_0(a) = 2^n,~ \hat{f}_1(a) = -2^n.$

Thus, for each a ∈ Zn
2 the value of $\hat{f}(a)$ characterizes where the function ƒ(x) lies in the range from ƒ₀(x) to ƒ₁(x). Bent functions are in a sense equidistant from all of these, so they are equally hard to approximate with any affine function.

Definition and properties

Rothaus defined a bent function as a Boolean function ƒ: Zn
2 → Z₂ whose Walsh transform has constant absolute value.

The simplest examples of bent functions, written in algebraic normal form, are F(x₁,x₂) = x₁x₂ and G(x₁,x₂,x₃,x₄) = x₁x₂ + x₃x₄. This pattern continues: x₁x₂ + x₃x₄ + ... + x_n − 1x_n is a bent function Zn
2 → Z₂ for every even n, but there is a wide variety of different types of bent functions as n increases.^[2] The sequence of values (−1)^ƒ(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

$\hat{f}(a) = W(2^n) (-1)^{f(a)},$

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

Rothaus proved that bent functions exist only for even n, and that for a bent function ƒ, $|\hat{f}(a)|=2^{n/2}$ for all a ∈ Zn
2.^[1] 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 ƒ and g are considered dual functions.^[3]

Every bent function has a Hamming weight (number of times it takes the value 1) of 2^{n − 1} ± 2^n/2 − 1, and in fact agrees with any affine function at one of those two numbers of points. So the nonlinearity of ƒ (minimum number of times it equals any affine function) is 2^n − 1 − 2^n/2 − 1, the maximum possible. Conversely, any Boolean function with nonlinearity 2^n − 1 − 2^n/2 − 1 is bent.^[1] The degree of ƒ in algebraic normal form (called the nonlinear order of ƒ) is at most n/2 (for n > 2).^[2]

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^[4] or those arising from a monomial over a finite field,^[5] but so far the bent functions have defied all attempts at a complete enumeration or classification.

Applications

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.^[6] 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.^[7] Indeed, the functions satisfying the SAC to the highest possible order are always bent.^[8] Furthermore, the bent functions are as far as possible from having what are called linear structures, nonzero vectors a such that ƒ(x+a) + ƒ(x) is a constant. In the language of differential cryptanalysis (introduced after this property was discovered) the derivative of a bent function ƒ at every nonzero point a (that is, ƒ_a(x) = ƒ(x+a) + ƒ(x)) is a balanced Boolean function, taking on each value exactly half of the time. This property is called perfect nonlinearity.^[2]

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.^[2] But functions produced in this way may lose other desirable properties, even failing to satisfy the SAC—so careful testing is necessary.^[8] 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.^[9][10][11]

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.^[11] The cryptographic hash function HAVAL uses Boolean functions built from representatives of all four of the equivalence classes of bent functions on six variables.^[12] The stream cipher Grain uses an NLFSR whose nonlinear feedback polynomial is, by design, the sum of a bent function and a linear function.^[13]

Generalizations

The most common class of generalized bent functions is the mod m type, $f:\mathbb{Z}_m^n \to \mathbb{Z}_m$ such that

$\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. Perfect nonlinear functions $f:\mathbb{Z}_m^n \to \mathbb{Z}_m$, those such that for all nonzero a, ƒ(x+a) − ƒ(a) takes on each value m^n − 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.^[14]

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 $|\hat{f}|$ 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.^[15]

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.^[16]

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ⁿ), 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 Zn
2 → Zn
2, such as almost bent functions and crooked functions. While not Boolean functions themselves, these are closely related to the bent functions and have good nonlinearity properties.

References

1. ^ ^{a b c} C. Qu; J. Seberry, T. Xia (29 December 2001). Boolean Functions in Cryptography. http://citeseer.ist.psu.edu/old/700097.html. Retrieved 14 September 2009. 
2. ^ ^{a b c d} W. Meier; O. Staffelbach (April 1989). "Nonlinearity Criteria for Cryptographic Functions". Eurocrypt '89. pp. 549–562. 
3. ^ ^{a b} C. Carlet; L.E. Danielsen, M.G. Parker, P. Solé (19 May 2008). "Self Dual Bent Functions" (PDF). Fourth International Workshop on Boolean Functions: Cryptography and Applications (BFCA '08). http://www.ii.uib.no/~matthew/bfcasdb.pdf. Retrieved 21 September 2009. 
4. ^ T. Xia; J. Seberry, J. Pieprzyk, C. Charnes (June 2004). "Homogeneous bent functions of degree n in 2n variables do not exist for n > 3". Discrete Applied Mathematics 142 (1-3): 127–132. doi:10.1016/j.dam.2004.02.006. ISSN 0166-218X. http://ro.uow.edu.au/infopapers/291/. Retrieved 21 September 2009. 
5. ^ A. Canteaut; P. Charpin, G. Kyureghyan (January 2008). "A new class of monomial bent functions" (PDF). Finite Fields and Their Applications 14 (1): 221–241. doi:10.1016/j.ffa.2007.02.004. ISSN 1071-5797. http://www-roc.inria.fr/secret/Anne.Canteaut/Publications/CanChaKuy07.pdf. Retrieved 21 September 2009. 
6. ^ J. Olsen; R. Scholtz, L. Welch (November 1982). "Bent-Function Sequences". IEEE Transactions on Information Theory IT-28 (6): 858–864. ISSN 0018-9448. http://www.costasarrays.org/costasrefs/b2hd-olsen82bent-function.html. Retrieved 24 September 2009. 
7. ^ R. Forré (August 1988). "The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition". CRYPTO '88. pp. 450–468. 
8. ^ ^{a b} C. Adams; S. Tavares (January 1990). The Use of Bent Sequences to Achieve Higher-Order Strict Avalanche Criterion in S-Box Design. Technical Report TR 90-013. Queen's University. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8374. Retrieved 23 September 2009. 
9. ^ K. Nyberg (April 1991). "Perfect nonlinear S-boxes". Eurocrypt '91. pp. 378–386. 
10. ^ J. Seberry; X. Zhang (December 1992). "Highly Nonlinear 0-1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion". AUSCRYPT '92. pp. 143–155. http://citeseerx.ist.psu.edu:80/viewdoc/summary?doi=10.1.1.57.4992. Retrieved 24 September 2009. 
11. ^ ^{a b} C. Adams (November 1997). "Constructing Symmetric Ciphers Using the CAST Design Procedure". Designs, Codes, and Cryptography 12 (3): 283–316. doi:10.1023/A:1008229029587. ISSN 0925-1022. http://jya.com/cast.html. Retrieved 20 September 2009. 
12. ^ Y. Zheng; J. Pieprzyk, J. Seberry (December 1992). "HAVAL—a one-way hashing algorithm with variable length of output" (PDF). AUSCRYPT '92. pp. 83–104. http://labs.calyptix.com/files/haval-paper.pdf. Retrieved 24 September 2009. 
13. ^ M. Hell; T. Johansson, A. Maximov, W. Meier (PDF). A Stream Cipher Proposal: Grain-128. http://www.ecrypt.eu.org/stream/p2ciphers/grain/Grain128_p2.pdf. Retrieved 24 September 2009. 
14. ^ K. Nyberg (May 1990). "Constructions of bent functions and difference sets". Eurocrypt '90. pp. 151–160. 
15. ^ K. Khoo; G. Gong, D. Stinson (February 2006). "A new characterization of bent and semi-bent functions on finite fields" (PostScript). Designs, Codes, and Cryptography 38 (2): 279–295. doi:10.1007/s10623-005-6345-x. ISSN 0925-1022. http://www.cacr.math.uwaterloo.ca/~dstinson/papers/dcc-final.ps. Retrieved 24 September 2009. 
16. ^ Y. Zheng; X. Zhang (November 1999). "Plateaued Functions". Second International Conference on Information and Communication Security (ICICS '99). pp. 284–300. http://citeseer.ist.psu.edu/old/291018.html. Retrieved 24 September 2009. 

Further reading

• C. Carlet (May 1993). "Two New Classes of Bent Functions". Eurocrypt '93. pp. 77–101. 
• J. Seberry; X. Zhang (March 1994). "Constructions of Bent Functions from Two Known Bent Functions". Australasian Journal of Combinatorics 9: 21–35. ISSN 1034-4942. http://citeseerx.ist.psu.edu:80/viewdoc/summary?doi=10.1.1.55.531. Retrieved 17 September 2009. 
• T. Neumann; advisor: U. Dempwolff (May 2006). Bent Functions. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.8731. Retrieved 23 September 2009. 
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2006). Handbook of Combinatorial Designs (2nd ed.). CRC Press. pp. 337–339. ISBN 978-1-58-488506-1.