Generalizations of Bent Functions. A Survey 1
---
paper_title: Generalized bent functions and their properties

paper_content:

Abstract Jet Jqm denote the set of m-tuples over the integers modulo q and set i= −1 , w = e i( 2π q ) . As an extension of Rothaus' notion of a bent function, a function f, f: Jqm → Jq1 is called bent if all the Fourier coefficients of wf have unit magnitude. An important feature of these functions is that their out-of-phase autocorrelation value is identically zero. The nature of the Fourier coefficients of a bent function is examined and a proof for the non-existence of bent functions over Jqm, m odd, is given for many values of q of the form q = 2 (mod 4). For every possible value of q and m (other than m odd and q = 2 (mod 4)), constructions of bent functions are provided.
---
paper_title: q-ary Bent Functions Constructed from Chain Rings

paper_content:

A chain ring is a finite local principal ideal ring.q-ary bent functions are constructed from chain rings which are freeZ"q-modules. A construction combining such bent functions is also given.
---
paper_title: Monomial and quadratic bent functions over the finite fields of odd characteristic

paper_content:

Considered are p-ary bent functions having the form f(x)=Tr/sub n/(/spl sigma//sub i=0//sup s/a/sub i/x/sup di/). A new class of ternary monomial regular bent function with the Dillon exponent is discovered. The existence of Dillon bent functions in the general case is an open problem of deciding whether a certain Kloosterman sum can take on the value -1. Also described is the general Gold-like form of a bent function that covers all the previously known monomial quadratic cases. The (weak) regularity of the new as well as of known monomial bent functions is discussed and the first example of a not weakly regular bent function is given. Finally, some criteria for an arbitrary quadratic function to be bent are proven.
---
paper_title: Bent-function sequences

paper_content:

In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parameter n with n=0 \pmod{4} , the period of the sequences is 2^{n}-1 , the number of sequences in the set is 2^{n/2} , and the cross/auto correlation function has three values with magnitudes \leq 2^{n/2}+1 . The equivalent linear span of the codes is bound above by \sum_{i=1}^{n/4}\left(\stackrel{n}{i} \right) . These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing.
---
paper_title: p-Ary and q-ary versions of certain results about bent functions and resilient functions

paper_content:

Using the Teichmuller character and Gauss sums, we obtain the following results concerning p-ary bent functions and q-ary resilient functions: (1) a characterization of certain q-ary resilient functions in terms of their coefficients; (2) stronger upper bounds for the degree of p-ary bent functions; (3) determination of all bent functions on F"p; (4) a characterization of ternary weakly regular bent functions in terms of their coefficients.
---
paper_title: Generalized bent functions and their properties

paper_content:

Abstract Jet Jqm denote the set of m-tuples over the integers modulo q and set i= −1 , w = e i( 2π q ) . As an extension of Rothaus' notion of a bent function, a function f, f: Jqm → Jq1 is called bent if all the Fourier coefficients of wf have unit magnitude. An important feature of these functions is that their out-of-phase autocorrelation value is identically zero. The nature of the Fourier coefficients of a bent function is examined and a proof for the non-existence of bent functions over Jqm, m odd, is given for many values of q of the form q = 2 (mod 4). For every possible value of q and m (other than m odd and q = 2 (mod 4)), constructions of bent functions are provided.
---
paper_title: Connections between Quaternary and Binary Bent Functions

paper_content:

Boolean bent functions were introduced by Rothaus (1976) as combinatorial objects related to difference sets, and have since enjoyed a great popularity in symmetric cryptography and low correlation sequence design. In this paper direct links between Boolean bent functions, generalized Boolean bent functions (Schmidt, 2006) and quaternary bent functions (Kumar, Scholtz, Welch, 1985) are explored. We also study Gray images of bent functions and notions of generalized nonlinearity for functions that are relevant to generalized linear cryptanalysis.
---
paper_title: Bent Rectangles ∗

paper_content:

We study generalized regular bent functions using a representation by bent rectangles, that is, special matrices with restrictions on rows and columns. We describe affine transformations of bent rectangles, propose new biaffine and bilinear constructions, study partitions of a vector space into affine planes of the same dimension and use such partitions to build bent rectangles. We illustrate the concept of bent rectangles by examples for the Boolean case.
---
paper_title: Quaternary Constant-Amplitude Codes for Multicode CDMA

paper_content:

A constant-amplitude code is a code that reduces the peak-to-average power ratio (PAPR) in multicode code-division multiple access (MC-CDMA) systems to the favorable value 1. In this paper quaternary constant-amplitude codes (codes over Z_4) of length 2^m with error-correction capabilities are studied. These codes exist for every positive integer m, while binary constant-amplitude codes cannot exist if m is odd. Every word of such a code corresponds to a function from the binary m-tuples to Z_4 having the bent property, i.e., its Fourier transform has magnitudes 2^{m/2}. Several constructions of such functions are presented, which are exploited in connection with algebraic codes over Z_4 (in particular quaternary Reed-Muller, Kerdock, and Delsarte-Goethals codes) to construct families of quaternary constant-amplitude codes. Mappings from binary to quaternary constant-amplitude codes are presented as well.
---
paper_title: On codes with low peak-to-average power ratio for multi-code CDMA

paper_content:

Multi-code CDMA (MC-CDMA) was demonstrated to provide a simple, rate-increasing enhancement to existing CDMA systems. MC-CDMA systems suffer from high peak-to-average power ratio (PAPR), and several authors have considered ad hoc coding methods to alleviate this problem. Here, we make a systematic study of the use of coding to reduce the PAPR in MC-CDMA systems.
---
paper_title: Connections between Quaternary and Binary Bent Functions

paper_content:

Boolean bent functions were introduced by Rothaus (1976) as combinatorial objects related to difference sets, and have since enjoyed a great popularity in symmetric cryptography and low correlation sequence design. In this paper direct links between Boolean bent functions, generalized Boolean bent functions (Schmidt, 2006) and quaternary bent functions (Kumar, Scholtz, Welch, 1985) are explored. We also study Gray images of bent functions and notions of generalized nonlinearity for functions that are relevant to generalized linear cryptanalysis.
---
paper_title: Highly nonlinear mappings

paper_content:

Functions with high nonlinearity have important applications in cryptography, sequences and coding theory. The purpose of this paper is to give a well-rounded treatment of non-Boolean functions with optimal nonlinearity. We summarize and generalize known results, and prove a number of new results. We also present open problems about functions with high nonlinearity.
---
paper_title: Nonlinearities of S-boxes

paper_content:

We introduce an indicator of the non-balancedness of functions defined over Abelian groups, and deduce a new indicator, denoted by NB, of the nonlinearity of such functions. We prove an inequality relating NB and the classical indicator NL, introduced by Nyberg and studied by Chabaud and Vaudenay, of the nonlinearity of S-boxes. This inequality results in an upper bound on NL which unifies Sidelnikov-Chabaud-Vaudenay's bound and the covering radius bound. We also deduce from bounds on linear codes three new bounds on NL that improve upon Sidelnikov-Chabaud-Vaudenay's bound and the covering radius bound in many cases.
---
paper_title: Generalized boolean bent functions

paper_content:

The notions of perfect nonlinearity and bent functions are closely dependent on the action of the group of translations over $\mathbb{F}^{m}_{2}$. Extending the idea to more generalized groups of involutions without fixed points gives a larger framework to the previous notions. In this paper we largely develop this concept to define G-perfect nonlinearity and G-bent functions, where G is an Abelian group of involutions, and to show their equivalence as in the classical case.
---
paper_title: On Plateaued Functions

paper_content:

The focus of this article is on nonlinear characteristics of cryptographic Boolean functions. First, we introduce the notion of plateaued functions that have many cryptographically desirable properties. Second, we establish a sequence of strengthened inequalities on some of the most important nonlinearity criteria, including nonlinearity, avalanche, and correlation immunity, and prove that critical cases of the inequalities coincide with characterizations of plateaued functions. We then proceed to prove that plateaued functions include as a proper subset all partially bent functions that were introduced earlier by Claude Carlet (1993). This solves an interesting problem that arises naturally from previously known results on partially bent functions. In addition, we construct plateaued, but not partially bent, functions that have many properties useful in cryptography.
---
paper_title: On Plateaued Functions and Their Constructions

paper_content:

We use the notion of covering sequence, introduced by C. Carlet and Y. Tarannikov, to give a simple characterization of bent functions. We extend it into a characterization of plateaued functions (that is bent and three-valued functions). After recalling why the class of plateaued functions provides good candidates to be used in cryptosystems, we study the known families of plateaued functions and their drawbacks. We show in particular that the class given as new by Zhang and Zheng is in fact a subclass of Maiorana-McFarland’s class. We introduce a new class of plateaued functions and prove its good cryptographic properties.
---
paper_title: Relationships between Bent Functions and Complementary Plateaued Functions

paper_content:

We introduce the concept of complementary plateaued functions and examine relationships between these newly defined functions and bent functions. Results obtained in this paper contribute to the further understanding of profound secrets of bent functions. Cryptographic applications of these results are demonstrated by constructing highly nonlinear correlation immune functions that possess no non-zero linear structures.
---
paper_title: Cryptographer’s toolkit for construction of 8-bit bent functions

paper_content:

Boolean functions form basic building blocks in various cryptographic algorithms. They are used for instance as filters in stream ciphers. Maximally non-linear (necessarily non-balanced) Boolean functions with an even number of variables are called bent functions. Bent functions can be modified to get balanced highly non-linear Boolean functions. Recently the first author has demonstrated how bent functions can be studied in a recursive framework of certain integer-valued functions. Based on this new approach we describe the practical systematic construction of 8-bit bent functions. We outline also how to compute the number of all 8-bit bent functions.
---
paper_title: On the degree of homogeneous bent functions

paper_content:

In this paper, the degree of homogeneous bent functions is discussed. We prove that for any nonnegative integer k, there exists a positive integer N such that for n>=N there exist no 2n- variable homogeneous bent functions having degree n-k or more, where N is the least integer satisfying 2^N^-^1>N+10+N+11+...+N+1k+1.
---
paper_title: Homogeneous bent functions

paper_content:

This paper discusses homogeneous bent functions. The space of homogeneous functions of degree three in six boolean variables was exhaustively searched and 30 bent functions were found. These are found to occur in a single orbit under the action of relabeling of the variables. The homogeneous bent functions identified exhibit interesting combinatorial structures and are, to the best of our knowledge, the first examples of bent functions without quadratic terms. A construction for other homogeneous bent functions of degree three in larger spaces is also given.
---
paper_title: Semi-bent functions

paper_content:

Highly nonlinear balanced Boolean functions both satisfying the propagation criterion and having almost uniform correlation values with all linear functions are very important in the design of hash functions, stream and block ciphers. In particular, the output uncorrelated properties between two Boolean functions are required to design permutations. We present, so called, semi-bent functions which satisfy all of these properties.
---
paper_title: Partially-Bent Functions

paper_content:

We study a conjecture stated in [6] about the numbers of non-zeros of, respectively, the auto-correlation function and the Walsh transform of the function (-l)f(x) where f(x) is any boolean (unction on {0, l}n. The result that, we obtain leads us to introduce the class of partially-bent functions. We study within these functions the propagation criterion. We characterize those partially-bent functions which are balanced and prove a relation between their number (which is unknown) and the number of non-balanced partially-bent functions on {0.1}n-1. Eventually, we study their correlation immunity.
---
paper_title: Generalized Partially Bent Functions

paper_content:

Based on the definition of generalized partially bent functions, using the theory of linear transformations, the relationship between generalized partially Bent functions over ring ZN and generalized bent functions over ring ZN is discussed. Assume that N is a prime number, it is proved that some generalized partially Bent functions can be decomposed as the addition of a generalized bent function and an affine function. The decomposition facilitates the easy understanding and construction of partially Bent functions and generalized partially Bent functions. The result obtained here generalizes the main work concerning partially Bent functions by Claud Carlet. Finally, an approach to construct generalized Bent functions using the Rudin-Shapiro construction is derived.
---
paper_title: Transform Domain Analysis of DES

paper_content:

The Data Encryption Standard (DES) can be regarded as a nonlinear feedback shift register (NLFSR) with input. From this point of view, the tools for pseudo-random sequence analysis are applied to the S-boxes in DES. The properties of the S-boxes of DES under the Fourier transform, Hadamard transform, extended Hadamard transform, and the Avalanche transform are investigated. Two important results about the S-boxes of DES are found. The first result is that nearly two-thirds of the total 32 functions from GF (2/sup 6/) to GF(2) which are associated with the eight S-boxes of DES have the maximal linear span G3, and the other one-third have linear span greater than or equal to 57. The second result is that for all S-boxes, the distances of the S-boxes approximated by monomial functions has the same distribution as for the S-boxes approximated by linear functions. Some new criteria for the design of permutation functions for use in block cipher algorithms are discussed.
---
paper_title: Hyper-bent functions and cyclic codes

paper_content:

Bent functions are those Boolean functions whose Hamming distance to the Reed-Muller code of order 1 equal 2n-1) - 2n/2-1 (where the number n of variables is even). These combinatorial objects, with fascinating properties, are rare. Few constructions are known, and it is difficult to know whether the bent functions they produce are peculiar or not, since no way of generating at random bent functions on 8 variables or more is known.The class of bent functions contains a subclass of functions whose properties are still stronger and whose elements are still rarer. Youssef and Gong have proved the existence of such hyperbent functions, for every even n. We prove that the hyper-bent functions they exhibit are exactly those elements of the well-known PIap class, introduced by Dillon, up to the linear transformations x ↦ δx, δ ∈ F2n*. Hyper-bent functions seem still more difficult to generate at random than bent functions; however, by showing that they all can be obtained from some codewords of an extended cyclic code Hn with small dimension, we can enumerate them for up to 10 variables. We study the non-zeroes of Hn and we deduce that the algebraic degree of hyper-bent functions is n/2. We also prove that the functions of class PIap are some codewords of weight 2n-1 - 2n/2-1 of a subcode of Hn and we deduce that for some n, depending on the factorization of 2n - 1, the only hyperbent functions on n variables are the elements of the class PIap#, obtained from PIap by composing the functions by the transformations x ↦ δx, δ ≠ 0, and by adding constant functions. We prove that non-PIap# hyper-bent functions exist for n = 4, but it is not clear whether they exist for greater n. We also construct potentially new bent functions for n = 12.
---
paper_title: Hyper-bent Functions

paper_content:

Bent functions have maximal minimum distance to the set of affine functions. In other words, they achieve the maximal minimum distance to all the coordinate functions of affine monomials. In this paper we introduce a new class of bent functions which we call hyper-bent functions. Functions within this class achieve the maximal minimum distance to all the coordinate functions of all bijective monomials. We provide an explicit construction for such functions. We also extend our results to vectorial hyper-bent functions.
---
paper_title: Generalized hyper-bent functions over GF(p)

paper_content:

In this paper, we extend the concept of binary hyper-bent functions introduced by Carlet to functions defined over GF(p). We show that such functions must be quadratic. We also provide the necessary and sufficient conditions on the symmetric coefficient matrix corresponding to the quadratic form of f:Z"p^n->Z"p that guarantee that f is a hyper-bent function.
---
paper_title: A new cryptanalytic attack for PN-generators filtered by a Boolean function

paper_content:

We present a new cryptanalytic attack on PN-generators filtered by a Boolean function. The key-idea is to jointly combine the knowledge of the Boolean function and the LFSR structure so as to introduce a new iterative decoding technique. The results we obtained prove to be very good: indeed, even in the case of systems for which classical iterative algorithms appear powerless, our scheme enables us to recover the LFSR initial state with a very low error probability. The latter is such that ending the algorithm by an exhaustive search among sequences of limited length is hardly needed. Therefore, the overall complexity of our scheme remains very small and the algorithm appears as an excellent candidate for cryptanalysis of filtered PN-generators.
---
paper_title: Near bent functions on a hyperplane

paper_content:

We present a general criterion for near bent functions to be bent on a hyperplane. Let n=3k+/-1 be odd and let d=4^k-2^k+1. We show that the Kasami-Welch function Tr(x^d) is a bent function when restricted to the hyperplane of trace 0 elements in F"2"^"n.
---
paper_title: Constructing Large Cryptographically Strong S-boxes

paper_content:

While there is evidence that large substitution boxes (S-boxes) have better cryptographic properties than small S-boxes, they are much harder to design. The difficulty arises from the relative scarcity of suitable boolean functions as the size of the S-box increases. We describe the construction of cryptographically strong 5×5 S-boxes using near-bent boolean functions of five variables. These functions, where the number of variables is odd, possess highly desirable cryptographic properties and can be generated easily and systematically. Moreover, the S-boxes they compose are shown to satisfy all the important design criteria. Further, we feel that it is possible to generalize near-bent functions to any odd number of variables, thereby making construction of yet larger S-boxes feasible.
---
paper_title: On the Higher Order Nonlinearities of Boolean Functions and S-Boxes, and Their Generalizations

paper_content:

The r-th order nonlinearity of a Boolean function $f:F_2^n\to F_2$ is its minimum Hamming distance to all functions of algebraic degrees at most r, where ris a positive integer. The r-th order nonlinearity of an S-box $F:F_2^n\to F_2^m$ is the minimum r-th order nonlinearity of its component functions v·F, $v\in F_2^m\setminus \{0\}$. The role of this cryptographic criterion against attacks on stream and block ciphers has been illustrated by several papers. Its study is also interesting for coding theory and is related to the covering radius of Reed-Muller codes (i.e. the maximum multiplicity of errors that have to be corrected when maximum likelihood decoding is used on a binary symmetric channel). We give a survey of what is known on this parameter, including the bounds involving the algebraic immunity of the function, the bounds involving the higher order nonlinearities of its derivatives, and the resulting bounds on the higher order nonlinearities of the multiplicative inverse functions (used in the S-boxes of the AES). We show an improvement, when we consider an S-box instead of a Boolean function, of the bounds on the higher order nonlinearity expressed by means of the algebraic immunity. We study a generalization (for S-boxes) of the notion and we give new results on it.
---
paper_title: On Boolean functions which are bent and negabent

paper_content:

Bent functions f : F2m → F2 achieve largest distance to all linear functions. Equivalently, their spectrum with respect to the Hadamard-Walsh transform is flat (i.e. all spectral values have the same absolute value). That is equivalent to saying that the function f has optimum periodic autocorrelation properties. Negaperiodic correlation properties of f are related to another unitary transform called the nega-Hadamard transform. A function is called negabent if the spectrum under the nega-Hadamard transform is flat. In this paper, we consider functions f which are simultaneously bent and negabent, i.e. which have optimum periodic and negaperiodic properties. Several constructions and classifications are presented.
---
paper_title: Description of k-bent functions in four variables

paper_content:

A simple description is given of the class of 2-bent functions in four variables. This class consists of 384 quadratic functions with 12 distinct types of the quadratic part, which classifies all k-bent functions with at most four variables.
---
paper_title: Generalized Bent Criteria for Boolean Functions (I)

paper_content:

Generalisations of the bent property of a boolean function are presented, by proposing spectral analysis with respect to a well-chosen set of local unitary transforms. Quadratic boolean functions are related to simple graphs and it is shown that the orbit generated by successive Local Complementations on a graph can be found within the transform spectra under investigation. The flat spectra of a quadratic boolean function are related to modified versions of its associated adjacency matrix.
---
paper_title: On the Bent Boolean Functions That are Symmetric

paper_content:

Bent functions are the boolean functions having the maximal possible Hamming distance from the linear boolean functions. Bent functions were introduced and first studied by O. S. Rothaus in 1976.We prove that there are exactly four symmetric bent functions on every even number of variables. These functions are exactly the four symmetric quadratic polynomials of the given number of variables.
---
paper_title: On quadratic approximations in block ciphers

paper_content:

We consider quadratic approximations (of Boolean functions) of a special form and their potential applications in block cipher cryptanalysis. We show that the use of k-bent functions as ciphering functions extremely increases the resistance of ciphers to such approximations. We consider examples of 4-bit permutations recommended for use in S-boxes of the algorithms GOST 28147-89, DES, and s 3DES; we show that in almost all cases there exist more probable (than linear) quadratic relations of a special form on input and output bits of these permutations.
---

Title: Generalizations of Bent Functions. A Survey 1

Section 1: Introduction
Description 1: Discuss the motivation and structure of the survey, provide background information, and outline the covered generalizations of bent functions.

Section 2: Algebraic Generalizations of Bent Functions
Description 2: Present various algebraic generalizations including q-valued bent functions, bent functions over a finite field, generalized Boolean bent functions, bent functions on a finite abelian group with values in complex numbers or another finite abelian group, vector G-bent functions, and multidimensional bent functions.

Section 3: Combinatorial Generalizations of Bent Functions
Description 3: Explore generalizations based on combinatorial ideas, such as partially defined bent functions, plateaued functions, Z-bent functions, and homogeneous bent functions.

Section 4: Cryptographic Generalizations of Bent Functions
Description 4: Examine bent functions tailored for cryptographic applications, including balanced bent functions, partially bent functions, hyper-bent functions, near-bent functions, bent functions of higher nonlinearity order, and k-bent functions.

Section 5: Quantum Generalizations of Bent Functions
Description 5: Investigate quantum-related generalizations such as negabent functions, bent-4 functions, and I-bent functions.