HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, a bent function is a special type of
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 function ...
which is maximally non-linear; it is as different as possible from the set of all
linear Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...
and
affine function In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generall ...
s when measured by
Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
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 argume ...
. 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 statistic ...
between the output of the function and a linear function is minimal. In addition, the derivatives of a bent function are a 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 defense against
linear cryptanalysis In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two mos ...
. 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 aff ...
. 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 grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
, but have also been applied to
spread spectrum In telecommunication and radio communication, spread-spectrum techniques are methods by which a signal (e.g., an electrical, electromagnetic, or acoustic signal) generated with a particular bandwidth is deliberately spread in the frequency d ...
,
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 data storage. Codes are studied ...
, 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 which 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 Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
. The Walsh transform of a Boolean function f:\Z_2^n \to \Z_2 is the function \hat:\Z_2^n \to \Z given by :\hat(a) = \sum_ (-1)^ where is the
dot product In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an alg ...
in Z. Alternatively, let and . Then and hence :\hat(a) = \left, S_0(a)\ - \left, S_1(a)\ = 2 \left, S_0(a)\ - 2^n. For any Boolean function ''f'' and the transform lies in the range :-2^n \leq \hat(a) \leq 2^n. Moreover, the linear function and the affine function correspond to the two extreme cases, since : \hat_0(a) = 2^n,~ \hat_1(a) = -2^n. Thus, for each the value of \hat(a) 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 f:\Z_2^n \to \Z_2 whose
Walsh transform The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
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 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 logical formulas in one of three subforms: * The entire formula is purely tru ...
, are and . This pattern continues: is a bent function \Z_2^n \to \Z_2 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 ...
, 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(a) = W\left(2^n\right) (-1)^, where ''W''(2''n'') is the natural-ordered
Walsh matrix In mathematics, a Walsh matrix is a specific square matrix of dimensions 2, where ''n'' is some particular natural number. The entries of the matrix are either +1 or −1 and its rows as well as columns are orthogonal, i.e. dot product i ...
and the sequence is treated as a
column vector In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m 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 n, c ...
. Rothaus proved that bent functions exist only for even ''n'', and that for a bent function ''f'', \left, \hat(a)\ = 2^\frac for all . In fact, \hat(a) = 2^\frac(-1)^, where ''g'' is also bent. In this case, \hat(a) = 2^\frac(-1)^, so ''f'' and ''g'' are considered dual functions. Every bent function has a
Hamming weight The Hamming weight of a 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 most typical case, a string ...
(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 often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, siz ...
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 power product, is a product of powers of variables with nonnegative integer expon ...
over a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, 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 sequence A maximum length sequence (MLS) is a type of pseudorandom binary sequence. They are bit sequences generated using maximal linear-feedback shift registers and are so called because they are periodic and reproduce every binary sequence (except th ...
s 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, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable ...
properties rivalling those of the Gold codes and Kasami codes 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 telecommunication and radio communication, spread-spectrum techniques are methods by which a signal (e.g., an electrical, electromagnetic, or acoustic signal) generated with a particular bandwidth is deliberately spread in the frequency d ...
techniques. The properties of bent functions are naturally of interest in modern digital
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
, 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 In cryptography, the avalanche effect is the desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions, wherein if an input is changed slightly (for example, flipping a single bit), the output changes ...
(SAC) and higher-order generalizations, and recommended this tool to select candidates for good S-boxes 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 ...
. 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 aff ...
(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 approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two mos ...
, 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 keystream ...
using a bent combining function is vulnerable to a
correlation attack In cryptography, correlation attacks are a class of known-plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear-feedback shift registers (LFSRs) using a Boolean function. Correlation ...
. 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 operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified elementary components in the design of many cryptographic protocols and are widely used to encr ...
CAST-128 In cryptography, CAST-128 (alternatively CAST5) is a symmetric-key block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has also been approved for Government of Canada use by the Communic ...
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 of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography: * the probability of a particular n-bit output ...
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 a ...
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 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 legum ...
uses an
NLFSR A nonlinear-feedback shift register (NLFSR) is a shift register whose input bit is a non-linear function of its previous state. For an n-bit shift register ''r'' its next state is defined as: r_(b_0, b_1, b_2, \ldots, b_)=r_(b_1, b_2, \ldots, f(b ...
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, f:\mathbb_m^n \to \mathbb_m such that :\hat(a) = \sum_ e^ has constant absolute value ''m''''n''/2. Perfect nonlinear functions f:\mathbb_m^n \to \mathbb_m, 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 f:\mathbb_m^n \to \mathbb_m with ''n'' odd, such that \left, \hat\ 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, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
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.


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