Results on rotation symmetric bent functions

In this paper we analyze the combinatorial properties related to the Walsh spectra of rotation symmetric Boolean functions on even number of variables. These results are then applied in studying rotation symmetric bent functions. For the first time we could present an enumeration strategy for all the 10-variable rotation symmetric bent functions.     

On the <Emphasis Type="Italic">p</Emphasis>-ary (cubic) bent and plateaued (vectorial) functions

Plateaued functions play a significant role in cryptography, sequences for communications, and the related combinatorics and designs. Comparing to their importance, those functions have not been studied in detail in a general framework. Our motivation is to bring further results on the characterizations of bent and plateaued functions, and to introduce new tools which allow us firstly a better understanding of their structure and secondly to get methods for handling and designing such functions. We first characterize bent functions in terms of all even moments of the Walsh transform, and then plateaued (vectorial) functions in terms of the value distribution of the second-order derivatives. Moreover, we devote to cubic functions the characterization of plateaued functions in terms of the value distribution of the second-order derivatives, and hence this reveals non-existence of homogeneous cubic bent (and also (homogeneous) cubic plateaued for some cases) functions in odd characteristic. We use a rank notion which generalizes the rank notion of quadratic functions. This rank notion reveals new results about (homogeneous) cubic plateaued functions. Furthermore, we observe non-existence of a function whose absolute Walsh transform takes exactly 3 distinct values (one being zero). We finally provide a new class of functions whose absolute Walsh transform takes exactly 4 distinct values (one being zero).     

The eight variable homogeneous degree three bent functions

We determine the affine equivalence classes of the eight variable degree three homogeneous bent functions using a new algorithm. Our algorithm applies to general bent functions and can systematically determine the automorphism groups. We provide a partial verification of the enumeration of eight variable degree three homogeneous bent functions obtained by Meng et al. We determine the affine equivalence classes of these functions.     

Counting all bent functions in dimension eight 99270589265934370305785861242880

Based on the classification of the homogeneous Boolean functions of degree 4 in 8 variables we present the strategy that we used to count the number of all bent functions in dimension 8. There are $$99270589265934370305785861242880 \approx 2^{106}$$ such functions in total. Furthermore, we show that most of the bent functions in dimension 8 are nonequivalent to Maiorana?CMcFarland and partial spread functions.     

最优布尔函数的一个性质

Walsh谱只有3个值:0,±2m+2,且同时达到代数次数上界n-m-1和非线性度上界2n-1-2m+1的n元m阶弹性布尔函数(m>n/2-2)称为饱和最优函数(saturatedbest简写为SB).本文将给出关于SB函数非零谱值位置分布的一个性质,利用这一性质我们给出构造非线性度为56的4次7兀2阶弹性布尔函数的一种方法.     

Towards the classification of self-dual bent functions in eight variables

In this paper, we classify quadratic and cubic self-dual bent functions in eight variables with the help of computers. There are exactly four and 45 non-equivalent self-dual bent functions of degree two and three, respectively. This result is achieved by enumerating all eigenvectors with ± 1 entries of the Sylvester Hadamard matrix with an integer programming algorithm based on lattice basis reduction. The search space has been reduced by breaking the symmetry of the problem with the help of additional constraints. The final number of non-isomorphic self-dual bent functions has been determined by exploiting that EA-equivalence of Boolean functions is related to the equivalence of linear codes.     

On the degree of homogeneous bent functions

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 .     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

A new construction of bent functions based on {\mathbb{Z}} -bent functions

Dobbertin has embedded the problem of construction of bent functions in a recursive framework by using a generalization of bent functions called ${\mathbb{Z}}$ -bent functions. Following his ideas, we generalize the construction of partial spreads bent functions to partial spreads ${\mathbb{Z}}$ -bent functions of arbitrary level. Furthermore, we show how these partial spreads ${\mathbb{Z}}$ -bent functions give rise to a new construction of (classical) bent functions. Further, we construct a bent function on 8 variables which is inequivalent to all Maiorana–McFarland as well as PS _ap type bents. It is also shown that all bent functions on 6 variables, up to equivalence, can be obtained by our construction.     

p-Ary and q-ary versions of certain results about bent functions and resilient functions

Using the Teichmüller 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 ; (4) a characterization of ternary weakly regular bent functions in terms of their coefficients.     

The graph of minimal distances of bent functions and its properties

A notion of the graph of minimal distances of bent functions is introduced. It is an undirected graph (V, E) where V is the set of all bent functions in 2k variables and \((f, g) \in E\) if the Hamming distance between f and g is equal to \(2^k\). It is shown that the maximum degree of the graph is equal to \(2^k (2^1 + 1) (2^2 + 1) \cdots (2^k + 1)\) and all its vertices of maximum degree are quadratic bent functions. It is obtained that the degree of a vertex from Maiorana—McFarland class is not less than \(2^{2k + 1} - 2^k\). It is proven that the graph is connected for \(2k = 2, 4, 6\), disconnected for \(2k \ge 10\) and its subgraph induced by all functions EA-equivalent to Maiorana—McFarland bent functions is connected.     

Duality between bent functions and affine functions

A Boolean function in an even number of variables is called bent if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We prove that there is a duality between bent functions and affine functions. Namely, we show that affine function can be defined as a Boolean function that is at the maximal possible distance from the set of all bent functions.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

On homogeneous rotation symmetric bent functions

In this paper, we present partial results towards the conjectured nonexistence of homogeneous rotation symmetric bent functions having degree > 2.     

Finding nonnormal bent functions

The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension n/2 on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions.     

On the arithmetic Walsh coefficients of Boolean functions

We generalize to the arithmetic Walsh transform (AWT) some results which were previously known for the Walsh–Hadamard transform of Boolean functions. We first generalize the classical Poisson summation formula to the AWT. We then define a generalized notion of resilience with respect to an arbitrary statistical measure of Boolean functions. We apply the Poisson summation formula to obtain a condition equivalent to resilience for one such statistical measure. Last, we show that the AWT of a large class of Boolean functions can be expressed in terms of the AWT of a Boolean function of algebraic degree at most three in a larger number of variables.     

Walsh函数的一种新定义及快速算法设计

传统的Walsh函数是以Rademacher函数为基函数生成 .本文运用对称复制的观点 ,定义了一种新函数 G函数 ,并以G函数为基础 ,定义了四种序的Walsh函数 ,同时 ,运用序码分析方法 ,实现了两种序Walsh变换的快速算法设计 .     

Enumeration of the bent functions of least deviation from a quadratic bent function

We study a construction of the bent functions of least deviation from a quadratic bent function, describe all these bent functions of 2k variables, and show that the quantity of them is 2 ^k (2¹ + 1) ... (2 ^k + 1). We find some lower bound on the number of the bent functions of least deviation from a bent function of the Maiorana-McFarland class.