Search

Non-normal Boolean bent functions are one of the least understood classes of bent functions, and only a few difficult-to-find examples of such functions are known. In this paper, we consider the following two open problems on the normality of bent functions: 1. Do non-normal bent functions in 8 variables and degree 4 exist? 2. Do non-normal bent functions in the PS − ∖ PS a p class exist? We solve both of these problems by finding among the known PS bent functions in n = 8 variables a non-normal bent function in the PS − ∖ PS a p class. [ABSTRACT FROM AUTHOR]

The class of rotation symmetric functions is extremely rich in terms of cryptographical significance. However, few constructions of rotation symmetric bent functions, which can correspond to bent idempotent functions, have been presented in the literature. In this paper, for any even integer $ n\geq{4} $, we first construct an $ n $-variable rotation symmetric bent function by modifying the truth table of Rothaus's bent function on the vector space $ \mathbb{F}_2^n $, and then obtain a bent idempotent function by corresponding it to the finite field $ \mathbb{F}_{2^n} $. By generalizing the proposed $ n $-variable Boolean function, we obtain a family of Boolean functions which are rotation symmetric bent on the vector space $ \mathbb{F}_2^n $ and bent idempotent over the finite field $ \mathbb{F}_{2^n} $. [ABSTRACT FROM AUTHOR]

Boolean functions are fundamental building blocks in both discrete mathematics and computer science, with applications spanning from cryptography to coding theory. Bent functions, a subset of Boolean functions with maximal nonlinearity, are particularly valuable in cryptographic applications. This study introduces a novel equivalence relation among all Boolean functions and presents an algorithm to generate bent functions based on this relation. We systematically generated a collection of 10,000 bent functions over eight variables, all originating from the same equivalence class, and analyzed their structural complexity through rank determination. Our findings revealed the presence of at least five distinct affine classes of bent functions within this collection. By employing this construction, we devised an algorithm to generate a filter function capable of combining Boolean functions. This filter function can be dynamically adjusted based on a key, offering potential applications in symmetric cipher design, such as enhancing security or improving efficiency. [ABSTRACT FROM AUTHOR]

Cryptographic Boolean functions play an important role in the design of symmetric ciphers. Many cryptographic criteria such as balancedness, nonlinearity, correlation immunity and transparency order are connected with the Walsh support of a Boolean function. However, we still know little about the possible structure of the Walsh supports of Boolean functions. In 2005, Carlet and Mesnager studied the Walsh supports of Boolean functions and constructed a class of n -variable Boolean functions whose Walsh support is F 2 n ∖ { 0 } , for n ≥ 10. For n ≤ 6 , it can be verified using the computer that there is no Boolean function with the Walsh Support F 2 n ∖ { 0 }. However, concerning the values of n = 7 , 8 , 9 , it has been an open problem for many years. In this paper, we construct two classes of balanced Boolean functions with the maximum possible Walsh support F 2 n ∖ { 0 } , and partially solve this problem. The first class of functions are of odd variables with n ≥ 9 , and the second class of functions are constructed based on the Maiorana–McFarland bent functions, which are of even variables with n ≥ 8. As a result, the above open problem has been settled for n = 8 , 9 , and the only unsolved case is n = 7. [ABSTRACT FROM AUTHOR]

Boolean functions used in symmetric-key encryption should have high higher-order nonlinearity to resist several known cryptographic attacks, such as algebraic attacks and low-degree approximation attacks. The higher-order nonlinearity also plays an important role in coding theory and theoretical computer science, since it relates to the covering radius of Reed–Muller codes and the Gowers norm, respectively. It is well-known that bent functions have the highest nonlinearity in an even number of variables and thus they possess the best ability to withstand fast correlation attacks and best affine approximation attacks. However, there is currently limited knowledge regarding the higher-order nonlinearity of bent functions because computing the higher-order nonlinearity, or even providing tight lower bounds, is an extremely hard task. In 1974, Dillon proposed two well-known classes of bent functions based on partial spread (in brief, PS), called PS − and PS + , respectively. He also exhibited a subclass of bent functions in PS − , known as partial spread affine plane(PS a p for short). In this paper, we provide a lower bound on the third-order nonlinearity of the simplest PS a p bent functions in n variables, where n ≥ 6 is even, by calculating the nonlinearities of all second-order derivatives of this kind of bent functions. Compared to the two known lower bounds on the third-order nonlinearity given by Carlet and Tang et al. respectively, our lower bound is much better than these two ones. [ABSTRACT FROM AUTHOR]

In this paper we give three constructions of cyclic self-orthogonal codes over Z 2 k , for k ≥ 3 , from Boolean functions on n variables. The first construction for each k, 3 ≤ k ≤ n , yields a self-orthogonal Z 2 k -code of length 2 n + 2 with all Euclidean weights divisible by 2 k + 1. In the remaining two constructions, for each even n and k ≥ 3 , we generate a self-orthogonal Z 2 k -code of length 2 n + 1. All Euclidean weights in the constructed code are divisible by 2 2 k - 1 or 2 k + 1 , depending on which of the two constructions is used. [ABSTRACT FROM AUTHOR]

We present and analyze the relation between different types of linear codes through the (projective) dual transform. The considered codes are represented by a generator matrix or a characteristic vector, and the dual transform is defined in these terms. This allows us to extend its use to study codes with special properties, which we call self-polar, and their relation to Boolean functions. The self-polar codes are a special class of projective self-dual codes and are closely connected with self-dual and anti-self-dual bent functions. We also give some computational results for self-dual bent functions in eight variables. [ABSTRACT FROM AUTHOR]

In this paper, we study the value distributions of perfect nonlinear functions, i.e., we investigate the sizes of image and preimage sets. Using purely combinatorial tools, we develop a framework that deals with perfect nonlinear functions in the most general setting, generalizing several results that were achieved under specific constraints. For the particularly interesting elementary abelian case, we derive several new strong conditions and classification results on the value distributions. Moreover, we show that most of the classical constructions of perfect nonlinear functions have very specific value distributions, in the sense that they are almost balanced. Consequently, we completely determine the possible value distributions of vectorial Boolean bent functions with output dimension at most 4. Finally, using the discrete Fourier transform, we show that in some cases value distributions can be used to determine whether a given function is perfect nonlinear, or to decide whether given perfect nonlinear functions are equivalent. [ABSTRACT FROM AUTHOR]

Aaronson defined Forrelation (2010) as a measure of correlation between a Boolean function f and the Walsh–Hadamard transform of another function g . In a recent work, we have studied different cryptographically important spectra of Boolean functions through the lens of Forrelation. In this paper, we explore a similar kind of correlation in terms of nega-Hadamard transform. We call it nega-Forrelation and obtain a more efficient sampling strategy for nega-Hadamard transform compared to the existing results. Moreover, we present an efficient sampling strategy for nega-crosscorrelation (and consequently nega-autocorrelation) spectra too, by tweaking the nega-Forrelation technique. Finally, we connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it for the negabent functions. [ABSTRACT FROM AUTHOR]

A Boolean function f on n variables is said to be a bent function if the absolute value of all its Walsh coefficients is 2 n / 2 . Our main result is a new asymptotic lower bound on the number of Boolean bent functions. It is based on a modification of the Maiorana–McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. By-products of our proofs are the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into 2-dimensional affine and linear subspaces. [ABSTRACT FROM AUTHOR]

Recently, several interesting constructions of vectorial Boolean functions with the maximum number of bent components (MNBC functions, for short) were proposed. However, many of them have component functions from the completed Maiorana-McFarland class M # . Moreover, no examples of MNBC functions containing component functions provably outside M # are known. In this paper, we classify all MNBC functions in six variables. Based on the analysis of the obtained equivalence classes, we propose several infinite families of MNBC functions with component functions outside the M # class. In particular, two of our new constructions are solutions to the open problem [Bapić et al (eds) Proceedings of the twelfth international workshop on coding and cryptography, 2022, Item 1., p. 9]. [ABSTRACT FROM AUTHOR]

The substitution box (S-box) is the core component of any block cipher that creates confusion in the ciphertext. This research contributes to creating a substitution box based on bent Boolean functions. Bent Boolean functions are constructed using the Maiorana–McFarland method and used as the coordinate functions of the substitution box. They are maximal nonlinear and inherently imbalanced, making them unsuitable for direct use in constructing a confusion component. The imbalance nature of the coordinate Boolean function directly impacts the bijective property of the nonlinear component. To create a bijective confusion component, we focus on mitigating the imbalance of each coordinate Boolean function. The methodology adopted is simple and efficient as compared to other heuristic techniques. By defining an empty matrix and putting bent Boolean functions side by side as matrix elements, we shape the initial 2 n × k sized substitution box, k ∈ (2 ,... , n) . We limit the number of occurrences of each possible outcome of initial 2 n × k substitution box to make a bijective n × n S-box. These small initial S-boxes lay a good foundation for constructing strong subsequent S-boxes. Experimental results based on the generation of 8 × 8 substitution box indicate that the suggested algorithm outperforms other competing heuristic approaches in nonlinearity, while maintaining sufficient performance in the strict avalanche criterion, bit-independence, linear and differential probability properties. The suggested nonlinear component is tested using well-known images from the literature, and the histogram analysis of the confused images demonstrates a high degree of randomness. [ABSTRACT FROM AUTHOR]

Bent functions are Boolean functions in even number of variables that have maximal nonlinearity. They have flat Walsh–Hadamard spectrum and are of interest for their applications in algebra, coding theory and cryptography. A bent function is called self-dual if it coincides with its dual bent function. In current work we study the decomposition of the form f 0 , f 1 , ... , f 2 k - 1 of the vector of values of a self-dual bent function, formed by the concatenation of 2 k Boolean functions f j in n - k variables. We treat the cases k = 1 , 2 . Based on a spectral characterization, we introduce a notion of self-dual near-bent function in odd number of variables and prove that there exists a one-to-one correspondence between the notions of self-duality for even and odd number of variables. As a result the characterization for the decomposition f 0 , f 1 is obtained. For the decomposition f = f 0 , f 1 , f 2 , f 3 we prove that if sign vectors of subfunctions f j are linearly dependent, then all these subfunctions are bent. We prove that for n ⩾ 6 the converse does not hold, that is the obtained condition is sufficient only. These results are also generalized for the case of an arbitrary bent function. Three new iterative constructions of self-dual bent functions are proposed. One of them allows to build a class of self-dual bent functions which cannot be decomposed into the concatenation of four bent functions. Based on the constructions a new iterative lower bound on the cardinality of the set of self-dual bent functions is obtained. [ABSTRACT FROM AUTHOR]

Boolean functions form the fundamental components of symmetric cryptographic systems, serving as the building blocks. Modifying bent functions makes it feasible to design Boolean functions with desired properties that exhibit high non-linearity. The current study offers a comprehensive analysis of bent functions through its support, culminating in the introduction of an algorithm for the systematic construction of four variable bent functions. This algorithm enables the complete generation of all 896 fourvariable bent functions. Furthermore, we introduce a methodology for constructing n-variable bent functions (where n > 4), leveraging both the algorithm and an established secondary technique for bent function construction. Lastly, we examine the estimation of the count of bent functions by utilising certain properties associated with the support of bent functions. [ABSTRACT FROM AUTHOR]

Recently, balanced Boolean functions with an even number n of variables achieving very good autocorrelation properties have been obtained for 12 ≤ n ≤ 26 . These functions attain the maximum absolute value in the autocorrelation spectra (without considering the zero point) less than 2 n 2 and are found by using a heuristic search algorithm that is based on the design method of an infinite class of such functions for a higher number of variables. Here, we consider balanced Boolean functions that are closest to the bent functions in terms of the Hamming distance and perform a genetic algorithm efficiently aiming to optimize their cryptographic properties, which provides better absolute indicator values for all of those values of n for the first time. We also observe that among our results, the functions for 16 ≤ n ≤ 26 have nonlinearity greater than 2 n − 1 − 2 n 2 . In the process, our search strategy produces balanced Boolean functions with the best-known nonlinearity for 8 ≤ n ≤ 16 . [ABSTRACT FROM AUTHOR]

The influence of a variable is an important concept in the analysis of Boolean functions. The more general notion of influence of a set of variables on a Boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalizations of the Poincar\'e inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterizations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et al. [Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, BC, Canada, IEEE Computer Society, 2002, pp. 103--112] and Blais [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, M. Mitzenmacher, ed., Bethesda, MD, ACM, 2009, pp. 151--158] is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions does not satisfy one or more desirable properties that a notion of influence may be expected to satisfy. [ABSTRACT FROM AUTHOR]

Boosted by cryptography and coding theory applications and rich connections to objects from geometry and combinatorics, bent functions and related functions developed into a lively research area. In the mid-seventies, Rothaus initially introduced bent functions in the Boolean case, but later, they extended in the p-ary case where p is any prime. Such an extension brought more rich connections to bent functions. In addition to the theory of Fourier transform, handling p-ary bent functions (where p is an odd prime), analyzing their properties and designing them require using the theory of cyclotomic fields. Such a family is classified into weakly regular bent and regular bent. Compared to the Boolean case, the class of p-ary bent functions inherits a much larger variety of properties. For example, it contains the class of dual-bent functions as a proper subclass, which again includes weakly regular bent functions as a proper subclass. Weakly regular bent functions can also be employed in many domains. In particular, they have been widely used in designing good linear codes for several applications (such as secret sharing and two-party computation), association schemes, and strongly regular graphs. More exploration is still needed despite a lot of interest and attention in this topic to increase our knowledge of bent functions and design them. In particular, only a few constructions of weakly regular bent functions have been presented in the literature. Nice construction methods of these functions have been given by Tang et al (IEEE Trans Inf Theory 62(3):1166–1176, 2016). All the known infinite families of weakly regular bent functions belong to a class (denoted by Tang et al. in the previous reference) R F . This paper is devoted to weakly regular bent functions, and its objective is twofold. First, it aims to generate new infinite families of weakly regular bent functions living outside R F and secondly, to exploit the constructed functions to design new families of p-ary linear codes and investigate their use for some standard application after studying this minimality based on their weight distributions. More specifically, we present several classes of weakly regular bent functions obtained from monomial bent functions by modifying the values of some known weakly regular bent functions on some subsets of the finite field F p n (n is a positive integer). Our weakly regular bent functions are of degree either p or p + 1 2 . We also explicitly determine their corresponding dual functions. Finally, we exploit our constructions to derive four new classes of linear codes with three to seven weights. We also show that two of them lead to minimal codes, which are more appropriate for several concrete applications. [ABSTRACT FROM AUTHOR]

In this paper, we investigate when a balanced function can be a derivative of a bent function. We prove that every nonconstant affine function in an even number of variables n is a derivative of (2 n - 1 - 1) ∣ B n - 2 ∣ 2 bent functions, where B n is the set of all bent functions in n variables. Based on this result, we propose a new iterative lower bound for the number of bent functions. We study the property of balanced functions that depend linearly on at least one of their variables to be derivatives of bent functions. We show the connection between this property and the "bent sum decomposition problem". We use this connection to prove that if a balanced quadratic Boolean function is a derivative of a Boolean function, then this function is a derivative of a bent function. [ABSTRACT FROM AUTHOR]

Bent functions are maximally nonlinear Boolean functions. They are important functions introduced by Rothaus and studied firstly by Dillon and next by many researchers for more than four decades. A systematic construction method of bent functions by modifying the support of Rothaus's bent function was given in Su (IEEE Trans Inf Theory 66(5):3277–3291, 2020). In this paper, we give a further study on that construction method. Two more flexible construction methods of bent functions by modifying the support of Rothaus's bent function are given respectively. The newly constructed bent functions contain the result in Su (2020), which is simply a special subclass of the newly constructed bent functions. The dual functions of these bent functions are determined. The methods of constructing self-dual bent functions are given. And the numbers of the newly constructed bent functions are also presented. [ABSTRACT FROM AUTHOR]

Bent functions, semi-bent functions and other Boolean functions with a few Walsh spectra have important applications in coding theory, cryptography and sequence design. In this paper, motivated by the work of Tang et al.(IEEE Trans. Inf. Theory 63(10), 6149-6157, 2017), we provide several infinite families of bent, semi-bent functions and Boolean functions of $ n = 2m $ ($ m\ge 4 $ an integer) variables with five to thirteen-valued Walsh spectra by Kasami types, Gold-like types and Maiorana-MacFarland types. The conditions for these functions to be bent and semi-bent are sufficient and necessary. Furthermore, the dual functions of the new bent functions are given. The algebraic degree of the new functions range from $ 4 $ to $ m $ (or $ m+2 $ except for bent and semi-bent functions) and all the functions possess high nonlinearity. [ABSTRACT FROM AUTHOR]

The recently introduced concept of a bent partition of a $2m$ -dimensional vector space $\mathbb {V}_{2m}^{(p)}$ over a prime field $\mathbb {F}_{p}$ exhibits similar properties as a partition from a spread. In particular, it gives rise to a large family of bent functions obtained in the same manner as spread bent functions. We show that the first non-spread construction of bent partitions introduced by Pirsic and the third author ($p=2$), respectively, the first and the third author ($p$ odd), gives rise to a large variety of different bent partitions. Especially, we show that the sets of bent functions obtained with any two such bent partitions do not intersect. We then show that every union of sets from one of these bent partitions always forms a partial difference set. This generalizes some known results on partial difference sets from spreads. Some general results on partial difference sets from bent partitions of $\mathbb {V}_{2m}^{(2)}$ are given in the last section. [ABSTRACT FROM AUTHOR]

An interesting thread in the research of Boolean functions for cryptography and coding theory is the study of secondary constructions: given a known function with a good cryptographic profile, the aim is to extend it to a (usually larger) function possessing analogous properties. In this work, we continue the investigation of a secondary construction based on cellular automata (CA), focusing on the classes of bent and semi-bent functions. We prove that our construction preserves the algebraic degree of the local rule, and we narrow our attention to the subclass of quadratic functions, performing several experiments based on exhaustive combinatorial search and heuristic optimization through Evolutionary Strategies (ES). Finally, we classify the obtained results up to permutation equivalence, remarking that the number of equivalence classes that our CA-XOR construction can successfully extend grows very quickly with respect to the CA diameter. [ABSTRACT FROM AUTHOR]

A function $F: \mathbb {F}_{2}^{n}\rightarrow \mathbb {F} _{2}^{n}$ , $n=2m$ , can have at most $2^{n}-2^{m}$ bent component functions. Trivial examples are vectorial bent functions from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{m}$ , seen as functions on $\mathbb {F}_{2}^{n}$. The first nontrivial example is given in univariate form as $x^{2^{r}} {\rm Tr^{n}_{m}}(x), 1\le r < m$ (Pott et al. 2018), a few more examples of similar shape are given by Mesnager et al. 2019, and finally it has been shown that the quadratic function $F(x) = x^{2^{r}} {\rm Tr^{n}_{m}}(\Lambda (x))$ , has $2^{n}-2^{m}$ bent components if and only if $\Lambda $ is a linearized permutation polynomial of $\mathbb {F}_{2^{m}}[x]$ (Anbar et al. 2021). In the first part of this article, an upper bound for the nonlinearity of plateaued functions with $2^{n}-2^{m}$ bent components is shown, which is attained by the example $x^{2^{r}} {\rm Tr^{n}_{m}}(x)$. We then analyse in detail nonlinearity and differential spectrum of the class of functions $F(x) = x^{2^{r}} {\rm Tr^{n}_{m}}(\Lambda (x))$ , which, as will be seen, requires the study of the functions $x^{2^{r}}\Lambda (x)$. In the last part we demonstrate that this class belongs to a larger class of functions with $2^{n}-2^{m}$ Maiorana-McFarland bent components, which also contains nonquadratic and non-plateaued functions. [ABSTRACT FROM AUTHOR]

Designing of nonlinear confusion component of block cipher is one of the most important and inevitable research problem. Nowadays mostly heuristic search schemes were utilized for the construction of these confusion component. To construct, a cryptographically secure confusion component several algebraic structures were utilized. The thirst for new algebraic structure for the construction of these nonlinear confusion component has always been a point of interest. In this communication, we have utilized a maximal cyclic subgroup of unit of Galois ring. The offered algorithm is more general as compared to Galois field. The class of Boolean functions over Galois ring fall in mixed category which are not completely balanced. Boolean functions having higher nonlinearity and others cryptographic aspects added an inevitable significance in the construction of modern block ciphers. The primary idea of this article is to structure non-balanced Boolean functions on n variables, where n is an even integer, sustaining strict avalanche criterion (SAC) and bit independent criterion (BIC). By comparing SAC with available cryptographic Boolean functions, the constructed multivalued Boolean function acquire highest nonlinearity which does not follow the existing nonlinearity bound of Boolean functions. These newly proposed S-boxes consists of n basic Boolean functions which satisfy the balancedness and non-balancedness criterion. Therefore, these S-box structure lies within a less balanced and more bent Boolean function categories. [ABSTRACT FROM AUTHOR]

In this paper, we provide some sufficient conditions for a function of the form to be five-valued with the Walsh spectrum {0, ±2n/2, ±2n/2+1}. In particular, several classes of five-valued Walsh spectrum functions by adding the arbitrary product of linear functions to some known quadratic bent function are obtained. [ABSTRACT FROM AUTHOR]

In this paper we characterize the intersection of the completed Maiorana–McFarland class of bent functions M # and Carlet's D 0 class of bent functions. As a consequence of this characterization, we prove that when the degree of a permutation π is greater than 2 the Boolean function f (x , y) = x · π (y) + δ 0 (x) , with f : F 2 n × F 2 n → F 2 , is always outside M # class. This also refines the sufficient condition of Carlet, which claims that if π is not affine on some hyperplane then f ∉ M # . More precisely, this condition is also necessary when deg (π) = 2 , but it is not needed in the case deg (π) > 2 . We also specify a rather general framework for specifying bent functions in Carlet's C class which are provably outside the class M # . Finally, using ranks of bent functions, we investigate the intersection of the class C and the subclass of the partial spread class PS ap and prove that the probability that an n variable function in PS ap is also in C approaches zero as n increases. [ABSTRACT FROM AUTHOR]

In this paper, based on the theory of -valued quadratic forms we propose several classes of generalized Boolean bent functions over , and new families of codebooks are constructed from these functions. The codebooks constructed in this paper are nearly optimal with respect to the Welch bound, and their parameters are new. Furthermore, some Boolean bent functions are also derived. [ABSTRACT FROM AUTHOR]

Keywords: Boolean function; discrete Fourier (Walsh-Hadamard) transform; maximum nonlinearity; amplitude; dimension of a Boolean function; extension of general affine group EN Boolean function discrete Fourier (Walsh-Hadamard) transform maximum nonlinearity amplitude dimension of a Boolean function extension of general affine group 177 192 16 06/17/22 20220601 NES 220601 Note: Originally published in Diskretnaya Matematika (2021) 33,No2, 66-85 (in Russian). Discrete Fourier (Walsh-Hadamard) transform, dimension of a Boolean function, extension of general affine group, Boolean function, maximum nonlinearity, amplitude It is important to note the value of group invariants in problems connected to classification of Boolean functions. [Extracted from the article]

In this paper we investigate different questions related to bent–negabent functions. We first take an expository look at the state-of-the-art research in this domain and point out some technical flaws in certain results and fix some of them. Further, we derive a necessary and sufficient condition for which the functions of the form x · π (y) ⊕ h (y) [Maiorana–McFarland (M )] is bent–negabent, and more generally, we study the non-existence of bent–negabent functions in the M class. We also identify some functions that are bent–negabent. Next, we continue the recent work by Mandal et al. (Discrete Appl Math 236:1–6, 2018) on rotation symmetric bent–negabent functions and show their non-existence in larger classes. For example, we prove that there is no rotation symmetric bent–negabent function in 4 p k variables, where p is an odd prime. We present the non-existence of such functions in certain classes that are affine transformations of rotation symmetric functions. Keeping in mind the existing literature, we correct here some technical issues and errors found in other papers and provide some novel results. [ABSTRACT FROM AUTHOR]

Minimal codes are characterized by the property that none of the codewords is covered by some other linearly independent codeword. We first show that the use of a bent function g in the so-called direct sum of Boolean functions h (x , y) = f (x) + g (y) , where f is arbitrary, induces minimal codes. This approach gives an infinite class of minimal codes of length 2 n and dimension n + 1 (assuming that h : F 2 n → F 2 ), whose weight distribution is exactly specified for certain choices of f. To increase the dimension of these codes with respect to their length, we introduce the concept of non-covering permutations (referring to the property of minimality) used to construct a bent function g in s variables, which allows us to employ a suitable subspace of derivatives of g and generate minimal codes of dimension s + s / 2 + 1 instead. Their exact weight distribution is also determined. In the second part of this article, we first provide an efficient method (with easily satisfied initial conditions) of generating minimal [ 2 n , n + 1 ] linear codes that cross the so-called Ashikhmin–Barg bound. This method is further extended for the purpose of generating minimal codes of larger dimension n + s / 2 + 2 , through the use of suitable derivatives along with the employment of non-covering permutations. To the best of our knowledge, the latter method is the most general framework for designing binary minimal linear codes that violate the Ashikhmin–Barg bound. More precisely, for a suitable choice of derivatives of h (x , y) = f (x) + g (y) , where g is a bent function and f satisfies certain minimality requirements, for any fixed f, one can derive a huge class of non-equivalent wide binary linear codes of the same length by varying the permutation ϕ when specifying the bent function g (y 1 , y 2) = ϕ (y 2) · y 1 in the Maiorana–McFarland class. The weight distribution is given explicitly for any (suitable) f when ϕ is an almost bent permutation. [ABSTRACT FROM AUTHOR]

Boolean functions with five-valued Walsh spectra (shortened as five-valued functions) and semi-bent functions are two classes of Boolean functions with high nonlinearity. They have useful applications in cryptography and communications. In this paper, we first present the construction of resilient five-valued functions by modifying the support of Rothaus's bent function. And then, we give the method of constructing resilient semi-bent functions. At the same time, the number of the newly constructed resilient semi-bent functions is determined. Lastly, we give the construction of resilient semi-bent functions with maximal algebraic degree. [ABSTRACT FROM AUTHOR]

In this article, we propose two secondary constructions of bent functions without any conditions on initial bent functions employed by these methods. It is shown that both methods generate bent functions that belong to the generalized Maiorana–McFarland ( GMM n / 2 + k ) class of n-variable Boolean functions, with n even. The class GMM n / 2 + k contains functions that can be viewed as a concatenation of (n / 2 - k) -variable (not necessarily distinct) affine functions, which was previously (mainly) used in the design of resilient Boolean functions. Most notably, we show that a subclass of bent functions generated by our first method is provably outside the completed Maiorana–McFarland class MM # . This extremely large class of Boolean functions GMM n / 2 + k , which is shown to properly include the standard Maiorana–McFarland class MM , may contain a significant subset of bent functions that are not the members of MM # . In general, the inclusion of these bent functions, that are provably outside MM # , into the completed partial spread class remains unknown. [ABSTRACT FROM AUTHOR]

It has been shown that all the known binary Golay complementary sequences of length 2 m can be obtained by a single binary Golay complementary array of dimension m and size 2 × 2 × ⋯ × 2 which can be represented by a Boolean function. However, the construction of new binary Golay complementary sequences of length 2 m or Golay complementary arrays remains an open problem. In this paper, we studied the Walsh spectrum distribution and the nega spectrum distribution of the binary or quaternary Golay (Type-I) complementary array. Then, the Walsh spectrum of the binary Type-II complementary array and the nega spectrum of the binary Type-III complementary array are investigated as well. At last, the Walsh spectrum of a binary array in a complementary array set of size 4 is discussed. This work proves that binary and quaternary complementary arrays above-mentioned can only be constructed from (generalized) Boolean functions satisfying spectral values given in this paper. For instance, a binary Type-I complementary array must be bent for even m and near-bent for odd m with respect to the Walsh spectrum, and it must be negaplateaued, nega-bent or negalandscape with respect to the nega spectrum. On the other hand, constructions of new binary and quaternary complementary arrays may help us find new (generalized) Boolean functions with specific condition, such as bent or nega-bent functions. [ABSTRACT FROM AUTHOR]

In 2017, Tang et al. have introduced a generic construction for bent functions of the form f (x) = g (x) + h (x) , where g is a bent function satisfying some conditions and h is a Boolean function. Recently, Zheng et al. (Discret Math 344:112473, 2021) generalized this result to construct large classes of bent vectorial Boolean functions from known ones in the form F (x) = G (x) + h (X) , where G is a vectorial bent and h is a Boolean function. In this paper, we further generalize this construction to obtain vectorial bent functions of the form F (x) = G (x) + H (X) , where H is also a vectorial Boolean function. This allows us to construct new infinite families of vectorial bent functions, EA-inequivalent to G, which was used in the construction. Most notably, specifying H (x) = h (T r 1 n (u 1 x) , ... , T r 1 n (u t x)) , the function h : F 2 t → F 2 t can be chosen arbitrarily, which gives a relatively large class of different functions for a fixed function G. We also propose a method of constructing vectorial (n, n)-functions having maximal number of bent components. [ABSTRACT FROM AUTHOR]

Three classes of (balanced) Boolean functions with few Walsh transform values derived from bent functions, Gold functions and the product of linearized polynomials are obtained in this paper. Further, the value distributions of their Walsh transform are also determined by virtue of the property of bent functions, the Walsh transform property of Gold functions and the -tuple balance property of trace functions respectively. [ABSTRACT FROM AUTHOR]

Rotation symmetric bent functions are a special class of Boolean functions, and their construction is of theoretical and practical interest. In this paper, we propose a generic construction of rotation symmetric bent functions by modifying the support of a known class of quadratic rotation symmetric bent functions, which generalizes some earlier works. Moreover, many infinite classes of rotation symmetric bent functions with maximal algebraic degree can be easily obtained from our construction. [ABSTRACT FROM AUTHOR]

Properties of a secondary bent function construction that adds the indicator of an affine subspace of arbitrary dimension to a given bent function in n variables are obtained. Some results regarding normal and weakly normal bent functions are generalized. An upper bound for the number of generated bent functions is proven. This bound is attained if and only if the given bent function is quadratic. In certain cases, the addition of the indicator of an m-dimensional subspace, for different m, will not generate bent functions. Such examples are presented for any even n ≥ 10. It is proven that there exists an infinite family of Maiorana–McFarland bent functions such that the numbers of generated bent functions differ for the bent function and its dual function. [ABSTRACT FROM AUTHOR]

In Pasalic et al. (2016) a construction allowing for high levels of modification was presented. It can be used to construct several important combinatorial structures, among them are examples of complete permutations. Here the method is used to construct infinite classes of generalised complete permutations F (x) , where both F (x) and F (x) + h D (x) are permutations, not just F (x) + x. In the article three families of the function h D (x) are considered: h D (x) being a function multiplying the vector x with a vector D , a permutation matrix D , or a linear mapping matrix D. Most existing results related to complete permutations use the finite field notation, while in this article we are developing permutations based on the vector space structure. The case where D is a binary vector needs to be emphasised. In this case the permutation F (x) is defined in such a way that F (x) + D T x remains a permutation for any of the 2 n − 3 vectors D as defined in Eq. (5). Let S be the set of all such vectors. We present for arbitrary n > 4 construction of an S -complete permutation F (x) , where | S | = 2 n − 3 . Additionally, we prove that each of these permutations F has such a corresponding linear subspace L that the pair (F , L) satisfies the (C) -property and can be used to construct a huge infinite class of bent functions in Carlet's C class. In Mandal et al. (2016) it was proven that finding such pairs (F , L) is a difficult problem. [ABSTRACT FROM AUTHOR]

The objective of this article is to broaden the understanding of the connections between bent functions and partial difference sets. Recently, the first two authors showed that the elements which a vectorial dual-bent function with certain additional properties maps to 0, form a partial difference set, which generalizes the connection between Boolean bent functions and Hadamard difference sets, and some later established connections between p-ary bent functions and partial difference sets to vectorial bent functions. We discuss the effects of coordinate transformations. As all currently known vectorial dual-bent functions F : F p n → F p s are linear equivalent to l-forms, i.e., to functions satisfying F (β x) = β l F (x) for all β ∈ F p s , we investigate properties of partial difference sets obtained from l-forms. We show that they are unions of cosets of F p s ∗ , which also can be seen as certain cyclotomic classes. We draw connections to known results on partial difference sets from cyclotomy. Motivated by experimental results, for a class of vectorial dual-bent functions from F p n to F p s , we show that the preimage set of the squares of F p s forms a partial difference set. This extends earlier results on p-ary bent functions. [ABSTRACT FROM AUTHOR]

Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by C(ƒ) = {Tr(aƒ(x) + bx)x∈Fqm*: a, b ∈ Fqm}, where q is a prime power, Fqm* = Fqm \ {0}, Tr is the trace function from Fqm to Fq, and ƒ(x) is a function from Fqm to Fqm with ƒ(0) = 0. Almost bent functions, quadratic functions and some monomials on F2m were used in the first construction, and many families of binary linear codes with few weights were obtained in the literature. This paper studies some punctured codes of these binary codes. Several families of binary linear codes with few weights and new parameters are obtained in this paper. Several families of distance-optimal binary linear codes with new parameters are also produced in this paper. [ABSTRACT FROM AUTHOR]

Pott et al. (2018) showed that F(x) = x2rTrnm(x) , n = 2m , r ≥ 1, is a nontrivial example of a vectorial function with the maximal possible number 2n-2m of bent components. Mesnager et al. (2019) generalized this result by showing conditions on Λ (x) = x + ∑j=1σ αjx2tj, αj ∈ F2m, under which F(x) = x2rTrnm(Λ (x)) has the maximal possible number of bent components. We simplify these conditions and further analyse this class of functions. For all related vectorial bent functions F(x) = Trnm(γ F(x)) , γ ∈ F2n \ F2m, which as we will point out belong to the Maiorana-McFarland class, we describe the collection of the solution spaces for the linear equations DaF(x) = F(x) + F(x+a) + F(a) = 0 , which forms a spread of F2n. Analysing these spreads, we can infer neat conditions for functions H(x) = (F(x),G(x)) from F2n to F2m × F2m to exhibit small differential uniformity (for instance for Λ (x) = x and r=0 this fact is used in the construction of Carlet’s, Pott-Zhou’s, Taniguchi’s APN-function). For some classes of H(x) we determine differential uniformity and with a method based on Bezout’s theorem nonlinearity. [ABSTRACT FROM AUTHOR]

Let m be an even positive integer. A Boolean bent function ƒ on F2m-1 × F2 is called a cyclic bent function if for any a ≠ b ∈ F2m-1 and ε ∈ F2, ƒ(ax1, x2)+ ƒ(bx1, x2 + ε) is always bent, where x1 ∈ F2m-1, x2 ∈ F2. Cyclic bent functions look extremely rare. This paper focuses on cyclic bent functions on F2m-1 × F2 and their applications. The first objective of this paper is to establish a link between quadratic cyclic bent functions and a special type of prequasifields, and construct a class of quadratic cyclic bent functions from the Kantor-Williams prequasifields. The second objective is to use cyclic bent functions to construct families of optimal sequences. The results of this paper show that cyclic bent functions have nice applications in several fields such as coding theory, symmetric cryptography, and CDMA communication. [ABSTRACT FROM AUTHOR]

It is known that algebraic immunity of an n-variable Boolean function is upper bounded by [ ]. In literature, it was shown algebraic immunity of a subclass of Maiorana-McFarland (MM) bent Boolean functions is lower bounded by 2 and upper bounded by. In this paper, this lower bound is further improved. Given a Boolean function of -variables with algebraic immunity k ≥ 4, the improved lower bound helps a cryptographer to find a MM bent function of this class whose algebraic immunity is at least k − 2. [ABSTRACT FROM AUTHOR]

In this paper, we study the separation between the deterministic (classical) query complexity (D) and the exact quantum query complexity ( Q E ) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on n variables as the ones with minimum deterministic query complexity D(f). We observe that for each n, there exists a non-separable class of QF functions such that D (f) = Q E (f) . Further, we show that for some values of n, all the QF functions are non-separable. Then, we present QF functions for certain other values of n where separation can be demonstrated, in particular, Q E (f) = D (f) - 1 . In a related effort, we also study the Maiorana–McFarland (MM)-type Bent functions. We show that while for any MM Bent function f on n variables D (f) = n , separation can be achieved as n 2 ≤ Q E (f) ≤ ⌈ 3 n 4 ⌉ . Our results highlight how different classes of Boolean functions can be analyzed for classical–quantum separation exploiting the parity decision tree method. [ABSTRACT FROM AUTHOR]