
In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
, a bent function is a
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...
that is maximally non-linear; it is as different as possible from the set of all
linear
In mathematics, the term ''linear'' is used in two distinct senses for two different properties:
* linearity of a '' function'' (or '' mapping'');
* linearity of a '' polynomial''.
An example of a linear function is the function defined by f(x) ...
and
affine function
In Euclidean geometry, an affine transformation or affinity (from the Latin, ''wikt:affine, affinis'', "connected with") is a geometric transformation that preserves line (geometry), lines and parallel (geometry), parallelism, but not necessarily ...
s when measured by
Hamming distance
In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
between
truth tables
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional ar ...
. Concretely, this means the maximum
correlation
In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics ...
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 cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a Affinity_(law)#Terminology, relat ...
. 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
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...
.
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
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, but have also been applied to
spread spectrum
In telecommunications, especially radio communication, spread spectrum are techniques by which a signal (electrical engineering), signal (e.g., an electrical, electromagnetic, or acoustic) generated with a particular Bandwidth (signal processi ...
,
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
, and
combinatorial design
Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of ''balance'' and/or ''symmetry''. These co ...
. 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).]
Walsh transform
Bent functions are defined in terms of the Walsh transform. The Walsh transform of a Boolean function is the function given by
:
where is the dot product
In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a Scalar (mathematics), scalar as a result". It is also used for other symmetric bilinear forms, for example in a pseudo-Euclidean space. N ...
in Z.[ Alternatively, let and . Then and hence
:
For any Boolean function ''f'' and , the transform lies in the range
:
Moreover, the linear function and the affine function correspond to the two extreme cases, since
:
Thus, for each the value of characterizes where the function ''f''(''x'') lies in the range from ''f''0(''x'') to ''f''1(''x'').
]
Definition and properties
Rothaus defined a bent function as a Boolean function whose Walsh transform has constant absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if x is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...
. 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
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing propositional logic formulas in one of three subforms:
* The entire formul ...
, are and . This pattern continues: is a bent function for every even ''n'', but there is a wide variety of other bent functions as ''n'' increases.[ The sequence of values (−1)''f''(''x''), with taken in ]lexicographical order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
, 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''(2''n'') is the natural-ordered Walsh matrix and the sequence is treated as a column vector
In linear algebra, a column vector with elements is an m \times 1 matrix consisting of a single column of entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some , c ...
.[
Rothaus proved that bent functions exist only for even ''n'', and that for a bent function ''f'', for all .][ In fact, , where ''g'' is also bent. In this case, , so ''f'' and ''g'' are considered dual functions.][
Every bent function has a ]Hamming weight
The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the mo ...
(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
Homogeneity and heterogeneity are concepts relating to the uniformity of a substance, process or image. A homogeneous feature is uniform in composition or character (i.e., color, shape, size, weight, height, distribution, texture, language, i ...
ones[ or those arising from a ]monomial
In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered:
# A monomial, also called a power product or primitive monomial, is a product of powers of variables with n ...
over a finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
,[ but so far the bent functions have defied all attempts at a complete enumeration or classification.
]
Constructions
There are several types of constructions for bent functions.[
* 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
As early as 1982 it was discovered that maximum length sequences based on bent functions have cross-correlation
In signal processing, cross-correlation is a measure of similarity of two series as a function of the displacement of one relative to the other. This is also known as a ''sliding dot product'' or ''sliding inner-product''. It is commonly used f ...
and autocorrelation
Autocorrelation, sometimes known as serial correlation in the discrete time case, measures the correlation of a signal with a delayed copy of itself. Essentially, it quantifies the similarity between observations of a random variable at differe ...
properties rivalling those of the Gold code
A Gold code, also known as Gold sequence, is a type of binary sequence, used in telecommunications (CDMA) and satellite navigation ( GPS). Gold codes are named after Robert Gold. Gold codes have bounded small cross-correlations within a set, whi ...
s and Kasami code
Kasami sequences are binary sequences of length where is an even integer. Kasami sequences have good cross-correlation values approaching the Welch lower bound. There are two classes of Kasami sequences—the small set and the large set.
Kasami ...
s for use in CDMA
Code-division multiple access (CDMA) is a channel access method used by various radio communication technologies. CDMA is an example of multiple access, where several transmitters can send information simultaneously over a single communicatio ...
.[ These sequences have several applications in ]spread spectrum
In telecommunications, especially radio communication, spread spectrum are techniques by which a signal (electrical engineering), signal (e.g., an electrical, electromagnetic, or acoustic) generated with a particular Bandwidth (signal processi ...
techniques.
The properties of bent functions are naturally of interest in modern digital cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (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-box
In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Clau ...
es achieving near-perfect diffusion
Diffusion is the net movement of anything (for example, atoms, ions, molecules, energy) generally from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in Gibbs free energy or chemical p ...
.[ Indeed, the functions satisfying the SAC to the highest possible order are always bent.][ Furthermore, the bent functions are as far as possible from having what are called ''linear structures'', nonzero vectors a such that is a constant. In the language of ]differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...
(introduced after this property was discovered) the ''derivative'' of a bent function ''f'' at every nonzero point ''a'' (that is, is a ''balanced'' Boolean function, taking on each value exactly half of the time. This property is called ''perfect nonlinearity''.[
Given such good diffusion properties, apparently perfect resistance to differential cryptanalysis, and resistance by definition to ]linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a Affinity_(law)#Terminology, relat ...
, 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
stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystrea ...
using a bent combining function is vulnerable to a correlation attack
Correlation attacks are a class of cryptographic known-plaintext attacks for breaking stream ciphers whose keystreams are generated by combining the output of several linear-feedback shift registers (LFSRs) using a Boolean function. Correlation a ...
. 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.[ But functions produced in this way may lose other desirable properties, even failing to satisfy the SAC – so careful testing is necessary.][ 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.][
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
In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called ''blocks''. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage a ...
CAST-128 and CAST-256
In cryptography, CAST-256 (or CAST6) is a symmetric-key block cipher published in June 1998. It was submitted as a candidate for the Advanced Encryption Standard (AES); however, it was not among the five AES finalists. It is an extension of an ...
, makes use of bent functions.[ The ]cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map (mathematics), map of an arbitrary binary string to a binary string with a fixed size of n bits) that has special properties desirable for a cryptography, cryptographic application: ...
HAVAL uses Boolean functions built from representatives of all four of the equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
es of bent functions on six variables.[ The stream cipher ]Grain
A grain is a small, hard, dry fruit (caryopsis) – with or without an attached husk, hull layer – harvested for human or animal consumption. A grain crop is a grain-producing plant. The two main types of commercial grain crops are cereals and ...
uses an NLFSR whose nonlinear feedback polynomial is, by design, the sum of a bent function and a linear function.[
]
Generalizations
More than 25 different generalizations of bent functions are described in Tokareva's 2015 monograph.[ 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 ''m''''n''/2. Perfect nonlinear functions , those such that for all nonzero ''a'', takes on each value times, are generalized bent. If ''m'' is ]prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, 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 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.][
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
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
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 , 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
* Correlation immunity In mathematics, the correlation immunity of a Boolean function is a measure of the degree to which its outputs are uncorrelated with some subset of its inputs. Specifically, a Boolean function is said to be correlation-immune ''of order m'' if every ...
References
Further reading
*
*
*
*
{{DEFAULTSORT:Bent Function
Boolean algebra
Combinatorics
Symmetric-key cryptography
Theory of cryptography