# A Construction of Bent Functions ofn

Authors: Joan-Josep Climent; Francisco J. García; Verónica Requena
Journal: Algebra
 (2014)

---

## Abstract

We present a method to iteratively construct new bent functions ofn
+
2 variables from a bent function of n variables and its cyclic shift permutations using minterms of n variables and minterms of 2 variables. In addition, we provide the number of bent functions of n
+
2 variables that we can obtain by applying the method here presented, and finally we compare this method with a previous one introduced by us in 2008 and with the Rothaus and Maiorana-McFarland constructions.


---

## Body

## 1. Introduction

Boolean functions are widely used in different types of cryptographic applications, such as block ciphers, stream ciphers, and hash functions [1–3], and in coding theory [4, 5], among others. For example, the implementation of an S-box needs nonlinear Boolean functions to resist attacks such as the linear and differential cryptanalysis [6–9]. For an even number of variables, Boolean functions bearing maximum nonlinearity are called bent functions [10, 11]. The construction of one-to-one S-boxes so that any linear combination of the output functions is balanced has already been explained [12, 13] and also the issue of making such linear combination a bent function [14]. However, no conclusive approaches have been presented yet for the construction of all S-boxes so that they satisfy the property that any linear combination of the outputs is also bent. It is precisely for this reason that a thorough study of the properties of bent functions as well as of the methods to construct them has occupied the minds of many authors in the last decades (see, e.g., [9, 11, 15–35] and the references therein).Bent functions constitute a fascinating issue in cryptography but, unfortunately, there is a mist hovering over their properties, their classification, and their actual number. The origin of the concept of bent function takes us back to a theoretical article by McFarland [36] where he discussed difference sets in finite noncyclic groups. Dillon [24], a year later, systematized and further elaborated McFarland’s insights and provided proofs for a great number of properties; Dillon’s Ph.D. dissertation has been an excellent source in the field of bent functions up to the mid 1970s. But it was Rothaus [37] who came up with the name for the concept. These functions are called perfect nonlinear Boolean functions by Meier and Staffelbach [30].There are different ways to obtain bent functions; most of them are based on the algebraic normal form of a Boolean function and the Walsh transform. However, there are very few constructions of bent functions based on the truth table of Boolean functions, for example, the partial spread class of bent functions introduced by Dillon [24]; moreover, from the truth tables of linear functions and bent functions, it is possible to construct bent functions with a greater number of variables [38]. But not all the bent functions in 6 variables can be obtained from bent functions and linear functions with a smaller number of variables, as proved by Chang [21]. Hou and Langevin [28] described how, from a well-known bent function, new bent functions can be obtained with the same number of variables.Charnes et al. [39, 40] discovered a surprising relation with the classical invariant theory. Qu et al. [41] have found, by computer enumeration, an interesting class of bent functions with 6 variables. Carlet and Guillot [19], Dobbertin [25], Kumar et al. [29], and Langevin [42] have analyzed some bent function constructions, characterizations, properties, and generalizations. Tokareva [34] introduces lower bound on the number of bent functions that can be obtained by the iterative constructions proposed by Canteaut and Charpin [43].A general method for generating all bent functions is not known to exist yet, except for some particular cases. For example, it is well known that, forn
=
4, there are only 896 different bent functions, for n
=
6, Preneel [32] (see also [21]) proved that the number of different bent functions is 5
425
430
528, and, for n
=
8, Langevin and Leander [44] proved recently that the number of bent functions is 99
270
589
265
934
370
305
785
861
242
880. Nevertheless, the classification and counting for n
>
8 is still an open problem.We refer the reader to the two excellent surveys in [18] and [23, Chapter 5] about bent functions.The mentioned literature so far makes an intensive use of the representation of Boolean functions either in polynomial form, in matrix form, or in sequential form. Nevertheless, the classical concept of minterm, which, by the way, is directly related to the implementation of logic circuits and its complexity, has not been frequently applied (see [22]). This paper purports to practically generate bent functions using the representation of Boolean functions as a sum of minterms.The use of the algebraic normal form or the truth table or both has its advantages and disadvantages. For example, the algebraic normal form of a Boolean functionf
(
x
) of n variables provides directly its degree, and, if it is greater than n
/
2, we can ensure that f
(
x
) is not a bent function [37]; nevertheless, we do not know the cardinality of its support (i.e., the number of minterms). On the other hand, if we know the truth table of f
(
x
), then we know if its support has the necessary number of elements to be a bent function, although we do not know its degree.The remainder of the paper is organized as follows. In Section2, we present some basic definitions and notations used. In Section 3, we introduce a general method for the construction of bent functions of n
+
2 variables using a bent function of n variables and some of its shifts; we also introduce some other important results required to prove the main theorems. In Section 4, we present the necessary results to count the number of bent functions we can construct based on the method dealt with in Section 3. Finally, in Section 5, we show that our construction generates bent functions which are not Rothaus or Maiorana-McFarland type (see, e.g., [29, 37]); we also show that the construction introduced in this paper is basically different from the construction introduced in [22] and we compute the number of bent functions we can obtain using one construction but not by the other one. In addition, we summarize the number of bent functions obtained by the different methods here considered.


## 2. Preliminaries

Consider the binary fieldℤ
2 with the addition modulo 2 (denoted by ⊕) and the multiplication modulo 2. For any positive integer n, it is well known that ℤ
2
n is a linear space over ℤ
2 with the addition ⊕ given by
(1)
a
⊕
b
=
(
a
1
⊕
b
1
,
a
2
⊕
b
2
,
…
,
a
n
⊕
b
n
)
,
for a
=
(
a
1
,
a
2
,
…
,
a
n
) and b
=
(
b
1
,
b
2
,
…
,
b
n
) in ℤ
2
n. Also, we consider the inner product
(2)
〈
a
,
b
〉
=
a
1
b
1
⊕
a
2
b
2
⊕
⋯
⊕
a
n
b
n
,
of a and b. Furthermore, we say that a
<
b if there exists k (with 1
≤
k
≤
n) such that
(3)
a
1
=
b
1
,
a
2
=
b
2
,
…
,
a
k
-
1
=
b
k
-
1
with
a
k
=
0
,
b
k
=
1
.
So, we can order the elements e
0
,
e
1
,
…
,
e
2
n
-
1
∈
ℤ
2
n such that
(4)
e
0
<
e
1
<
⋯
<
e
2
n
-
1
.
Furthermore, if e
i
=
(
ϵ
1
(
i
)
,
ϵ
2
(
i
)
,
…
,
ϵ
n
(
i
)
)
∈
ℤ
2
n, then
(5)
ϵ
1
(
i
)
2
n
-
1
+
ϵ
2
(
i
)
2
n
-
2
+
⋯
+
ϵ
n
-
1
(
i
)
2
1
+
ϵ
n
(
i
)
2
0
=
i
∈
ℤ
2
n
and we call the vector e
i thebinary expansion of the integer i. With this representation, we can identify the vector e
i with the integer i and, consequently, we can identify the set ℤ
2
n with the set ℤ
2
n.ABoolean function of n variables is a map f
:
ℤ
2
n
→
ℤ
2. The set ℬ
n of all Boolean functions of n variables is a linear space over ℤ
2 with the addition ⊕ given by
(6)
(
f
⊕
g
)
(
x
)
=
f
(
x
)
⊕
g
(
x
)
,
for f
,
g
∈
ℬ
n. For a function f of ℬ
n, the (
0,1
)-sequence of length 2
n,
(7)
ξ
f
=
(
f
(
e
0
)
,
f
(
e
1
)
,
…
,
f
(
e
2
n
-
1
)
)
,
is called thetruth table of f. The truth table of a Boolean function can be obtained by its minterms. Aminterm on n variables x
1
,
x
2
,
…
,
x
n is an expression of the form
(8)
m
(
u
1
,
u
2
,
…
,
u
n
)
(
x
1
,
x
2
,
…
,
x
n
)
=
(
1
⊕
u
1
⊕
x
1
)
(
1
⊕
u
2
⊕
x
2
)
⋯
(
1
⊕
u
n
⊕
x
n
)
,
where (
u
1
,
u
2
,
…
,
u
n
)
∈
ℤ
2
n.Fori
=
0,1
,
2
,
…
,
2
n
-
1, it is evident that m
e
i
(
x
)
=
1 if and only if x
=
e
i. We will write m
i
(
x
) instead of m
e
i
(
x
). So, the truth table,
(9)
(
m
i
(
e
0
)
,
m
i
(
e
1
)
,
…
,
m
i
(
e
2
n
-
1
)
)
,
of m
i
(
x
) has 1 in the ith position and 0 elsewhere. Consequently,
(10)
⨁
i
=
0
2
n
-
1
m
i
(
x
)
=
1
.
Also, since m
i
(
x
)
=
m
j
(
x
) if and only if i
=
j, we can identify the minterm m
i
(
x
) with the integer i (or with the vector e
i as best suited).Now, for allf
∈
ℬ
n, it is well known that
(11)
f
(
x
)
=
⨁
i
=
0
2
n
-
1
f
(
e
i
)
m
i
(
x
)
and since the identity
(12)
⨁
i
=
0
2
n
-
1
a
i
m
i
(
x
)
=
0
implies a
i
=
0 for i
=
0,1
,
2
,
…
,
2
n
-
1, we can state that the set {
m
0
,
m
1
,
…
,
m
2
n
-
1
} is a basis of ℬ
n.For allf
∈
ℬ
n, we call thesupport of f the set
(13)
M
=
{
a
∈
ℤ
2
n
∣
f
(
a
)
=
1
}
or
M
=
{
i
∈
ℤ
2
n
∣
f
(
e
i
)
=
1
}
,
according to expression (11) and the identification of ℤ
2
n with ℤ
2
n. So, we can identify M as the set of minterms of f
(
x
). Therefore, we can rewrite expression (11) as
(14)
f
(
x
)
=
⨁
i
∈
M
m
i
(
x
)
,
where M
⊆
ℤ
2
n or M
⊆
ℤ
2
n as best suited.TheHamming weight of a (
0,1
)-sequence α, denoted by w
(
α
), is the number of 1s in α. The Hamming weight of a Boolean function f
(
x
), denoted by w
(
f
), is the Hamming weight of its truth table ξ
f; that is, w
(
f
)
=
w
(
ξ
f
), and consequently, w
(
f
) is the number of minterms in the expression of f
(
x
) taken as a sum of minterms. A (
0,1
)-sequence is balanced if it contains an equal number of 0s and 1s, so a function f in ℬ
n is balanced if its truth table is balanced.We say thatf
∈
ℬ
n is anaffine function if it takes the form
(15)
f
(
x
)
=
l
a
(
x
)
⊕
b
,
where a
∈
ℤ
2
n, l
a
(
x
)
=
〈
a
,
x
〉, and b
∈
ℤ
2. If b
=
0, f is called alinear function.Thenonlinearity of a function f
∈
ℬ
n is defined as
(16)
NL
(
f
)
=
min
⁡
{
d
(
f
,
φ
)
∣
φ
∈
𝒜
n
}
,
where 𝒜
n
⊆
ℬ
n is the set of all affine functions and the distance d
(
f
,
g
), for f
,
g
∈
ℬ
n, is defined as d
(
f
,
g
)
=
w
(
f
⊕
g
). The nonlinearity of f
∈
ℬ
n is upper bounded (see, e.g., [11, 18, 23, 30]) by
(17)
NL
(
f
)
≤
2
n
-
1
-
2
n
/
2
-
1
.
The Boolean functions achieving the maximum nonlinearity are calledbent functions (see, e.g., [11, 18, 23, 30]). As a consequence, bent functions only exist for n even.It is well know that the above upper bound on the nonlinearity of a Boolean function ofn variables coincides with the covering radius of the first order binary Reed-Muller code of length 2
n (see, e.g., [30, 45]).The following result (see, e.g., [11, 46]) that we quote for further references gives us a characterization of a bent function.Theorem 1.
Letf
(
x
) be a function of n variables. The following statements are equivalent. (1)
f
(
x
) is a bent function.
(2)
The Boolean functionf
(
x
)
⊕
f
(
x
⊕
a
) is balanced for all a
∈
ℤ
2
n
∖
{
0
}.
(3)
The number of1s in the truth table of the Boolean function f
(
x
)
⊕
l
a
(
x
) is 2
n
-
1
±
2
n
/
2
-
1 for all a
∈
ℤ
2
n.Taking into account that, and as a consequence of the previous theorem, iff
(
x
) is a bent function of n variables, then the number of 1s in its truth table is 2
n
-
1
±
2
n
/
2
-
1; so that w
(
f
)
=
2
n
-
1
±
2
n
/
2
-
1 and f
(
x
) is not balanced. Equivalently, f
(
x
) is expressed as a sum of 2
n
-
1
±
2
n
/
2
-
1 minterms.Finally, it is well known that for any bent functionf
(
x
), the functions 1
⊕
f
(
x
) and f
(
x
⊕
u
), for all u
∈
ℤ
2
n, are also bent functions.Before moving onto the next section, remember that two Boolean functionsf
(
x
) and g
(
x
) are calledaffine equivalent if there exist an n
×
n invertible matrix A, two vectors a
,
b
∈
ℤ
2
n, and a bit c
∈
ℤ
2 such that g
(
x
)
=
f
(
x
A
⊕
a
)
⊕
l
b
(
x
)
⊕
c.It is known (see, e.g., [47]) that affine equivalent functions are both bent or both not bent. So, many authors work on the problem offinding the number and representatives of affine equivalent classes of bent functions. Nevertheless, we are interested in the problem of finding how many different bent functions there exist or we can construct, because not all affine equivalent bent functions are different as we can see in the following example.Example 2.
Consider the bent function(18)
f
(
x
)

=

m
0
(
x
)
⊕
m
1
(
x
)
⊕
m
2
(
x
)
⊕
m
4
(
x
)
⊕
m
8
(
x
)
⊕
m
15
(
x
)
,
of 4 variables; the invertible matrix
(19)
A
=
[
0
0
0
1
0
0
1
1
0
1
0
1
1
1
1
0
]
,
the vectors a
=
(
0,0
,
0,1
), b
=
(
0,0
,
0,0
), and the bit c
=
0. It is easy to check that the Boolean functions f
(
x
A
⊕
a
)
⊕
l
b
(
x
)
⊕
c and f
(
x
) have both the same truth table and, consequently, are the same Boolean function.


## 3. Main Results

In the rest of the paper, we consider thatx
=
(
x
1
,
x
2
,
…
,
x
n
) is a vector of ℤ
2
n and that y
=
(
y
1
,
y
2
) is a vector of ℤ
2
2.Firstly, we introduce two important properties of the minterms which allow us to construct functions ofn
+
2 variables from functions of n variables. In the first one, for each minterm of n variables, we obtain four different minterms of n
+
2 variables.Lemma 3 (see Lemma 1 of [22]).
Suppose thata
∈
ℤ
2
n and b
∈
ℤ
2
2. If m
a
(
x
) is a minterm of n variables and m
b
(
y
) is a minterm of 2 variables, then m
c
(
y
,
x
)
=
m
b
(
y
)
m
a
(
x
) is a minterm of n
+
2 variables, where
(20)
c
=
b
1
2
n
+
1
+
b
2
2
n
+
a
,
b
=
b
1
2
+
b
2
.The previous lemma tells us that the four minterms ofn
+
2 variables, which can be obtained from the minterm m
a
(
x
) of n variables, are
(21)
m
a
(
y
,
x
)
,
m
2
n
+
a
(
y
,
x
)
,
m
2
n
+
1
+
a
(
y
,
x
)
,
m
2
n
+
2
n
+
1
+
a
(
y
,
x
)
.
Note that if we use the vector representation for the indices of the minterms, the four minterms of n
+
2 variables obtained from the minterm m
a
(
x
) of n variables are
(22)
m
(
0,0
,
a
)
(
y
,
x
)
,
m
(
0,1
,
a
)
(
y
,
x
)
,
m
(
1,0
,
a
)
(
y
,
x
)
,
m
(
1,1
,
a
)
(
y
,
x
)
.Furthermore, minterms have the following property that makes them operative from the algebraic point of view.Lemma 4.
One hasm
u
(
x
⊕
v
)
=
m
u
⊕
v
(
x
) for all u
,
v
∈
ℤ
2
n.Proof.
Assume that(23)
u
=
(
u
1
,
u
2
,
…
,
u
n
)
,
v
=
(
v
1
,
v
2
,
…
,
v
n
)
;
then
(24)
m
u
(
x
⊕
v
)
=
(
1
⊕
u
1
⊕
x
1
⊕
v
1
)
(
1
⊕
u
2
⊕
x
2
⊕
v
2
)
⋯
(
1
⊕
u
n
⊕
x
n
⊕
v
n
)
=
m
u
⊕
v
(
x
)
.The following theorem is the main result of this paper. Here, we present a construction of bent functions ofn
+
2 variables from a bent function f
(
x
) of n variables and some cyclic shifts of f
(
x
).Theorem 5.
Letf
(
x
) be a bent function of n variables and consider u
,
v
∈
ℤ
2
n. If σ is any permutation of {
0,1
,
2,3
}, then
(25)
B
(
y
,
x
)
=
m
σ
(
0
)
(
y
)
f
(
x
)
⊕
m
σ
(
1
)
(
y
)
f
(
x
⊕
u
)
⊕
m
σ
(
2
)
(
y
)
f
(
x
⊕
v
)
⊕
m
σ
(
3
)
(
y
)
(
1
⊕
f
(
x
⊕
u
⊕
v
)
)
is a bent function of n
+
2 variables.Proof.
According to Theorem1 we must prove that the Boolean function,
(26)
B
(
b
,
a
)
(
y
,
x
)
=
B
(
y
,
x
)
⊕
B
(
(
y
,
x
)
⊕
(
b
,
a
)
)
,
is balanced for all (
b
,
a
)
∈
ℤ
2
2
×
ℤ
2
n with (
b
,
a
)
≠
(
0
2
,
0
n
). In the following, we use the vector b
=
(
b
1
,
b
2
)
∈
ℤ
2
2 as the argument of the functions and its integer representation b
=
b
1
2
+
b
2
∈
ℤ
2
2 as subindex of a minterm. So, by Lemma 4,
(27)
B
(
b
,
a
)
(
y
,
x
)
=
B
(
y
,
x
)
⊕
B
(
y
⊕
b
,
x
⊕
b
)
=
m
σ
(
0
)
(
y
)
f
(
x
)
⊕
m
σ
(
1
)
(
y
)
f
(
x
⊕
u
)
⊕
m
σ
(
2
)
(
y
)
f
(
x
⊕
v
)
⊕
m
σ
(
3
)
(
y
)
(
1
⊕
f
(
x
⊕
u
⊕
v
)
)
⊕
m
σ
(
0
)
⊕
b
(
y
)
f
(
x
⊕
a
)
⊕
m
σ
(
1
)
⊕
b
(
y
)
f
(
x
⊕
u
⊕
a
)
⊕
m
σ
(
2
)
⊕
b
(
y
)
f
(
x
⊕
v
⊕
a
)
⊕
m
σ
(
3
)
⊕
b
(
y
)
(
1
⊕
f
(
x
⊕
u
⊕
v
⊕
a
)
)
.
Now, for eachb
∈
ℤ
2
2, if we denote by μ
b the permutation of {
0,1
,
2,3
} given by
(28)
μ
b
(
i
)
=
σ
(
i
)
⊕
b
for
i
=
0,1
,
2,3
,
then it is not difficult to prove that the 4
!
·
4 cases, corresponding to the different values of σ and b, are reduced to one of the following four cases for some permutation η of {
0,1
,
2,3
}.
(
1
) Consider
(29)
B
(
b
,
a
)
(
y
,
x
)
=
m
η
(
0
)
(
y
)
(
f
(
x
)
⊕
f
(
x
⊕
a
)
)
⊕
m
η
(
1
)
(
y
)
(
f
(
x
⊕
u
)
⊕
f
(
x
⊕
u
⊕
a
)
)
⊕
m
η
(
2
)
(
y
)
(
f
(
x
⊕
v
)
⊕
f
(
x
⊕
v
⊕
a
)
)
⊕
m
η
(
3
)
(
y
)
(
f
(
x
⊕
u
⊕
v
)
⊕
f
(
x
⊕
u
⊕
v
⊕
a
)
)
.
(
2
) Consider
(30)
B
(
b
,
a
)
(
y
,
x
)
=
m
η
(
0
)
(
y
)
(
f
(
x
)
⊕
f
(
x
⊕
u
⊕
a
)
)
⊕
m
η
(
1
)
(
y
)
(
f
(
x
⊕
u
)
⊕
f
(
x
⊕
a
)
)
⊕
m
η
(
2
)
(
y
)
(
f
(
x
⊕
v
)
⊕
f
(
x
⊕
u
⊕
v
⊕
a
)
⊕
1
)
⊕
m
η
(
3
)
(
y
)
(
f
(
x
⊕
u
⊕
v
)
⊕
f
(
x
⊕
v
⊕
a
)
⊕
1
)
.
(
3
) Consider
(31)
B
(
b
,
a
)
(
y
,
x
)
=
m
η
(
0
)
(
y
)
(
f
(
x
)
⊕
f
(
x
⊕
v
⊕
a
)
)
⊕
m
η
(
1
)
(
y
)
(
f
(
x
⊕
u
)
⊕
f
(
x
⊕
u
⊕
v
⊕
a
)
⊕
1
)
⊕
m
η
(
2
)
(
y
)
(
f
(
x
⊕
v
)
⊕
f
(
x
⊕
a
)
)
⊕
m
η
(
3
)
(
y
)
(
f
(
x
⊕
u
⊕
v
)
⊕
f
(
x
⊕
u
⊕
a
)
⊕
1
)
.
(
4
) Consider
(32)
B
(
b
,
a
)
(
y
,
x
)
=
m
η
(
0
)
(
y
)
(
f
(
x
)
⊕
f
(
x
⊕
u
⊕
v
⊕
a
)
⊕
1
)
⊕
m
η
(
1
)
(
y
)
(
f
(
x
⊕
u
)
⊕
f
(
x
⊕
v
⊕
a
)
)
⊕
m
η
(
2
)
(
y
)
(
f
(
x
⊕
v
)
⊕
f
(
x
⊕
u
⊕
a
)
)
⊕
m
η
(
3
)
(
y
)
(
f
(
x
⊕
u
⊕
v
)
⊕
f
(
x
⊕
a
)
⊕
1
)
.
Observe that each one of the factors which multiply to m
η
(
i
)
(
y
) for i
=
0,1
,
2,3 can be written as
(33)
f
(
z
)
⊕
f
(
z
⊕
a
)
or
f
(
z
)
⊕
f
(
z
⊕
a
)
⊕
1
mfm
for
z
∈
{
x
,
x
⊕
u
,
x
⊕
v
,
x
⊕
u
⊕
v
}
.
Now, by Theorem1, since f
(
z
)
⊕
f
(
z
⊕
a
) is balanced for all nonzero a, we have that B
(
b
,
a
)
(
y
,
x
) is balanced, unless a
=
b
=
0.Note that, as a consequence of Lemma4, if M is the support of f
(
x
), then
(34)
M
w
=
{
a
⊕
w
∣
a
∈
M
}
is the support of f
(
x
⊕
w
) for all w
∈
ℤ
2
n. Furthermore, as a consequence of Lemma 3, if we use the decimal notation for the indices of the minterms and consider the permutation (
0
2
n
2
n
+
1
2
n
+
2
n
+
1
b
0
b
1
b
2
b
3
), then the support of the bent function B
(
y
,
x
) constructed in Theorem 5 is the set
(35)
{
b
0
+
a
∣
a
∈
M
}
∪
{
b
1
+
a
∣
a
∈
M
u
}
∪
{
b
2
+
a
∣
a
∈
M
v
}
∪
{
b
3
+
a
∣
a
∈
M
u
⊕
v
}
.
Nevertheless, if we use the vector notation for the indices of the minterms and consider the permutation (
(
0,0
)
(
0,1
)
(
1,0
)
(
1,1
)
b
0
b
1
b
2
b
3
), then the support of B
(
y
,
x
) is the set
(36)
{
(
b
0
,
a
)
∣
a
∈
M
}
∪
{
(
b
1
,
a
)
∣
a
∈
M
u
}
∪
{
(
b
2
,
a
)
∣
a
∈
M
v
}
∪
{
(
b
3
,
a
)
∣
a
∈
M
u
⊕
v
}
.
Note that the sets of expression (35) (resp., (36)) are pairwise disjoints by Lemma 3.


## 4. Counting Bent Functions

In this section we introduce some results in order to compute the number of bent functions we can construct using Theorem5. Firstly, we consider three particular cases (see Corollaries 6, 7, and 8) which we can derive directly from Theorem 5. The first one corresponds to the case u
=
v
=
0; the second one to the case u
=
v
≠
0, and the third one to the case 0
≠
u
≠
v
≠
0.Corollary 6.
Iff
(
x
) is a bent function of n variables and σ is any permutation of {
0,1
,
2,3
}, then
(37)
F
f
(
y
,
x
)
=
(
m
σ
(
0
)
(
y
)
⊕
m
σ
(
1
)
(
y
)
⊕
m
σ
(
2
)
(
y
)
)
×
f
(
x
)
⊕
m
σ
(
3
)
(
y
)
(
1
⊕
f
(
x
)
)
is a bent function of n
+
2 variables.Corollary 7.
Iff
(
x
) is a bent function of n variables, u
∈
ℤ
2
n
∖
{
0
}, and σ is any permutation of {
0,1
,
2,3
}, then
(38)
G
f
,
u
(
y
,
x
)
=
m
σ
(
0
)
(
y
)
f
(
x
)
⊕
(
m
σ
(
1
)
(
y
)
⊕
m
σ
(
2
)
(
y
)
)
×
f
(
x
⊕
u
)
⊕
m
σ
(
3
)
(
y
)
(
1
⊕
f
(
x
)
)
is a bent function of n
+
2 variables.Corollary 8.
Iff
(
x
) is a bent function of n variables, u
,
v
∈
ℤ
2
n
∖
{
0
}, with u
≠
v, and σ is any permutation of {
0,1
,
2,3
}, then
(39)
H
f
,
u
,
v
(
y
,
x
)
=
m
σ
(
0
)
(
y
)
f
(
x
)
⊕
m
σ
(
1
)
(
y
)
f
(
x
⊕
u
)
⊕
m
σ
(
2
)
(
y
)
f
(
x
⊕
v
)
⊕
m
σ
(
3
)
(
y
)
(
1
⊕
f
(
x
⊕
u
⊕
v
)
)
is a bent function of n
+
2 variables.The following result establishes that the bent functions constructed in Corollary6 are all different from one another.Lemma 9.
Letf
(
x
) and g
(
x
) be bent functions of n variables. Assume that F
f
(
y
,
x
) is the bent function constructed in Corollary 6 using f
(
x
) and the permutation σ of {
0,1
,
2,3
}. Assume also that F
g
(
y
,
x
) is the bent function constructed in Corollary 6 using g
(
x
) and the permutation τ of {
0,1
,
2,3
}. If f
(
x
)
≠
g
(
x
), then F
f
(
y
,
x
)
≠
F
g
(
y
,
x
).Proof.
Ifξ and η are the truth tables of f
(
x
) and g
(
x
), respectively, then the truth tables of F
f
(
y
,
x
) and F
g
(
y
,
x
) have four blocks (not necessarily in that order and not the same order for all):
(40)
F
f
:
ξ
ξ
ξ
1
⊕
ξ
F
g
:
η
η
η
1
⊕
η
.
IfF
f
(
y
,
x
)
=
F
g
(
y
,
x
), then the four blocks of the second row are a permutation of the four blocks of the first row. But if we consider the 4
! cases corresponding to these permutations, we obtain that f
(
x
)
=
g
(
x
), or that f
(
x
) and g
(
x
) both have the same number of minterms and the complementary number of minterms. So, in all cases, we obtain a contradiction and, therefore, F
f
(
y
,
x
)
≠
F
g
(
y
,
x
).Our next result, whose proof is similar to the previous one, establishes that the bent functions constructed in Corollary7 are all different from one another.Lemma 10.
Letf
(
x
) and g
(
x
) be bent functions of n variables. Assume that G
f
,
u
(
y
,
x
) is the bent function constructed in Corollary 7 using f
(
x
), the vector u
∈
ℤ
2
n
∖
{
0
}, and the permutation σ of {
0,1
,
2,3
}. Assume also that G
g
,
a
(
y
,
x
) is the bent function constructed in Corollary 7 using g
(
x
), the vector a
∈
ℤ
2
n
∖
{
0
}, and the permutation τ of  {
0,1
,
2,3
}. If f
(
x
)
≠
g
(
x
), then G
f
(
y
,
x
)
≠
G
g
(
y
,
x
).The same result is not true for the bent functions constructed using Corollary8 as we can see in the following example.Example 11.
Assume thatn
=
2. Consider the vectors u
=
1
=
(
0,1
), v
=
2
=
(
1,0
) and the bent function f
(
x
)
=
m
0
(
x
). Then, according to expression (10), Lemmas 3 and 4, and Corollary 8, we have that
(41)
H
f
,
1
,
2
(
y
,
x
)
=
m
0
(
y
)
f
(
x
)
⊕
m
1
(
y
)
f
(
x
⊕
1
)
⊕
m
2
(
y
)
f
(
x
⊕
2
)
⊕
m
3
(
y
)
(
1
⊕
f
(
x
⊕
3
)
)
=
m
0
(
y
)
m
0
(
x
)
⊕
m
1
(
y
)
m
1
(
x
)
⊕
m
2
(
y
)
m
2
(
x
)
⊕
m
3
(
y
)
(
1
⊕
m
3
(
x
)
)
=
m
0
(
y
,
x
)
⊕
m
5
(
y
,
x
)
⊕
m
10
(
y
,
x
)
⊕
m
12
(
y
,
x
)
⊕
m
13
(
y
,
x
)
⊕
m
14
(
y
,
x
)
is a bent function of n
+
2
=
4 variables.
On the other hand, consider the vectorsa
=
1
=
(
0,1
) and b
=
3
=
(
1,1
) and the bent function g
(
x
)
=
m
1
(
x
). Again, by expression (10), Lemmas 3 and 4, and Corollary 8, we have that
(42)
H
g
,
1
,
3
(
y
,
x
)
=
m
1
(
y
)
g
(
x
)
⊕
m
0
(
y
)
g
(
x
⊕
1
)
⊕
m
2
(
y
)
g
(
x
⊕
3
)
⊕
m
3
(
y
)
(
1
⊕
g
(
x
⊕
2
)
)
=
m
0
(
y
,
x
)
⊕
m
5
(
y
,
x
)
⊕
m
10
(
y
,
x
)
⊕
m
12
(
y
,
x
)
⊕
m
13
(
y
,
x
)
⊕
m
14
(
y
,
x
)
,
is a bent function of n
+
2
=
4 variables. Clearly H
g
,
1
,
3
(
y
,
x
)
=
H
f
,
1
,
2
(
y
,
x
).Note that, in the previous example,g
(
x
)
=
f
(
x
⊕
1
) and that {
1
,
2
} and {
1
,
3
} are bases of the same linear subspace {
0
,
1
,
2
,
3
} of ℤ
2
2. With the aim to avoid this situation which provides equal bent functions, we will consider only vectors u
,
v
∈
ℤ
2
n such that {
u
,
v
} is a Gauss-Jordan basis of cardinality 2. Remember that a set {
u
1
,
u
2
,
…
,
u
k
}
⊆
ℤ
2
n is a Gauss-Jordan basis of cardinality k if the matrix whose rows are u
1
,
u
2
,
…
,
u
k is in reduced row echelon form (see also [48, 49]).So, our next result establishes that the bent functions constructed in Corollary8 are all different if {
u
,
v
} is a Gauss-Jordan basis of cardinality 2 of ℤ
2
n.Lemma 12.
Letf
(
x
) and g
(
x
) be bent functions of n variables. Assume that H
f
,
u
,
v
(
y
,
x
) is the bent function constructed in Corollary 8 using f
(
x
), the Gauss-Jordan basis {
u
,
v
} of cardinality 2 of ℤ
2
n, and the permutation σ of {
0,1
,
2,3
}. Assume also that H
g
,
a
,
b
(
y
,
x
) is the bent function constructed in Corollary 8 using g
(
x
), the Gauss-Jordan basis {
a
,
b
} of cardinality 2 of ℤ
2
n, and the permutation τ of {
0,1
,
2,3
}. If f
(
x
)
≠
g
(
x
), then H
f
,
u
,
v
(
y
,
x
)
≠
H
g
,
a
,
b
(
y
,
x
).Proof.
Ifξ and η are the truth tables of f
(
x
) and g
(
x
), respectively, then the truth tables of H
f
,
u
,
v
(
y
,
x
) and H
g
,
a
,
b
(
y
,
x
) have four blocks (not necessarily in that order and not the same order for all):
(43)
H
f
,
u
,
v
:
ξ
ξ
u
ξ
v
1
⊕
ξ
u
⊕
v
H
g
,
a
,
b
:
η
η
a
η
b
1
⊕
η
a
⊕
b
,
where ξ
u, ξ
v, ξ
u
⊕
v, η
a, η
b, and η
a
⊕
b are the truth tables of f
(
x
⊕
u
), f
(
x
⊕
v
), f
(
x
⊕
u
⊕
v
), g
(
x
⊕
a
), g
(
x
⊕
b
), and g
(
x
⊕
a
⊕
b
), respectively.
IfH
f
,
u
,
v
(
y
,
x
)
=
H
g
,
a
,
b
(
y
,
x
), then the four blocks of the second row are a permutation of the four blocks of the first row. But if we consider the 4
! cases corresponding to these permutations, we obtain that f
(
x
)
=
g
(
x
) or that f
(
x
) and g
(
x
) both have the same number of minterms and the complementary number of minterms, or that
(44)
(
a
,
b
)
∈
{
(
u
,
u
⊕
v
)
,
(
v
,
u
⊕
v
)
,
(
u
⊕
v
,
u
)
,
(
u
⊕
v
,
v
)
}
;
note that if {
u
,
v
} is a Gauss-Jordan basis of cardinality 2, then {
a
,
b
} cannot be a Gauss-Jordan basis of cardinality 2. So, in all cases we obtain a contradiction and, therefore, H
f
,
u
,
v
(
y
,
x
)
≠
H
g
,
a
,
b
(
y
,
x
).Our next result establishes that none of the bent functions, obtained by one of Corollaries6, 7, and 8, can be obtained by any of the others involved.Lemma 13.
Letf
(
x
), g
(
x
), and h
(
x
) be three bent functions of n variables (not necessarily different). Assume that F
f
(
y
,
x
) is the bent function constructed in Corollary 6 using f
(
x
) and the permutation σ of {
0,1
,
2,3
}. Assume that G
g
,
u
(
y
,
x
) is the bent function constructed in Corollary 7 using g
(
x
), the vector u
∈
ℤ
2
n
∖
{
0
}, and the permutation τ of {
0,1
,
2,3
}. Assume also that H
h
,
a
,
b
(
y
,
x
) is the bent function constructed in Corollary 8 using h
(
x
), the Gauss-Jordan basis {
a
,
b
} of cardinality 2 of ℤ
2
n, and the permutation ω of {
0,1
,
2,3
}. Then F
f
(
y
,
x
)
≠
G
g
,
u
(
y
,
x
), F
f
(
y
,
x
)
≠
H
h
,
a
,
b
(
y
,
x
), and G
g
,
u
(
y
,
x
)
≠
H
h
,
a
,
b
(
y
,
x
).Proof.
Ifξ, η, and ζ are the truth tables of f
(
x
), g
(
x
), and h
(
x
), respectively, then the truth tables of F
f
(
y
,
x
), G
g
,
u
(
y
,
x
), and H
h
,
u
,
v
(
y
,
x
) have four blocks (not necessarily in that order and not the same order for all):
(45)
F
f
:
ξ
ξ
ξ
1
⊕
ξ
G
g
,
u
:
η
η
u
η
u
1
⊕
η
H
h
,
a
,
b
:
ζ
ζ
a
ζ
b
1
⊕
ζ
a
⊕
b
,
where η
u, ζ
a, ζ
b, and ζ
a
⊕
b are the truth tables of g
(
x
⊕
u
), h
(
x
⊕
a
), h
(
x
⊕
b
), and h
(
x
⊕
a
⊕
b
), respectively.
The result is now evident becauseF
f
(
y
,
x
) has three identical blocks, G
g
,
u
(
y
,
x
) has only two identical blocks, and all the blocks of H
h
,
a
,
b
(
y
,
x
) are different.Now, as a consequence of the previous lemmas, we can obtain the number of bent functions ofn
+
2 variables that we can construct using Corollaries 6, 7, and 8.Theorem 14.
Ifν
n is the number of bent functions of n variables, then using Corollaries 6, 7, and 8 one can construct 2
2
n
+
2
ν
n different bent functions of n
+
2 variables.Proof.
According to Lemma9, using Corollary 6, we can construct
(46)
4
!
3
!
ν
n
,
bent functions of n
+
2 variables.
Similarly, according to Lemma10, using Corollary 7, we can construct
(47)
4
!
2
!
ν
n
(
2
n
-
1
)
,
bent functions of n
+
2 variables.
Finally, according to Lemma12, using Corollary 8, we can construct
(48)
4
!
ν
n
N
(
n
,
2
)
,
bent functions of n
+
2 variables where N
(
n
,
2
) is the number of Gauss-Jordan basis of cardinality 2 in ℤ
2
n. Now, taking into account that each linear subspace of dimension 2 has a unique Gauss-Jordan basis of cardinality 2, we have that N
(
n
,
2
) is the number of linear subspaces of dimension 2 in ℤ
2
n; so (see [50, page 46])
(49)
N
(
n
,
2
)
=
(
2
n
-
1
)
(
2
n
-
2
)
(
2
2
-
1
)
(
2
2
-
2
)
=
(
2
n
-
1
)
(
2
n
-
1
-
1
)
3
.
The result follows now by replacing expression (49) in expression (48) and by adding expressions (46), (47), and (48) because Lemma 13 guarantees that bent functions constructed according to Corollaries 6, 7, and 8 are all different from one another.


## 5. Comparison with Other Methods

Our examples now show some bent functions constructed according to Corollaries7 and 8 that are not Maiorana-McFarland functions or Rothaus functions.Example 15.
Assume thatn
=
2 and consider the bent function f
(
x
)
=
m
3
(
x
), the vector u
=
3
=
(
1,1
), and the permutation (
0
1
2
3
3
1
2
0
). Then Corollary 7, expression (10), and Lemmas 3 and 4 provide the bent function
(50)
G
(
y
,
x
)
=
m
3
(
y
)
m
3
(
x
)
⊕
(
m
1
(
y
)
⊕
m
2
(
y
)
)
m
0
(
x
)
⊕
m
0
(
y
)
(
1
⊕
m
3
(
x
)
)
=
m
15
(
y
,
x
)
⊕
m
4
(
y
,
x
)
⊕
m
8
(
y
,
x
)
⊕
m
0
(
y
,
x
)
⊕
m
1
(
y
,
x
)
⊕
m
2
(
y
,
x
)
=
1
⊕
x
1
x
2
⊕
y
1
y
2
⊕
y
1
x
1
⊕
y
1
x
2
⊕
y
2
x
1
⊕
y
2
x
2
,
which is not a Maiorana-McFarland function.Example 16.
Assume thatn
=
2 and consider the bent function f
(
x
)
=
m
1
(
x
), the vectors u
=
2
=
(
1,0
), v
=
1
=
(
0,1
), and the permutation (
0
1
2
3
0
3
1
2
). Then Corollary 8, expression (10), and Lemmas 3 and 4 provide the bent function
(51)
H
(
y
,
x
)
=
m
0
(
y
)
m
1
(
x
)
⊕
m
3
(
y
)
m
3
(
x
)
⊕
m
1
(
y
)
m
0
(
x
)
⊕
m
2
(
y
)
(
1
⊕
m
2
(
x
)
)
=
m
1
(
y
,
x
)
⊕
m
15
(
y
,
x
)
⊕
m
4
(
y
,
x
)
⊕
m
8
(
y
,
x
)
⊕
m
9
(
y
,
x
)
⊕
m
11
(
y
,
x
)
=
x
2
⊕
x
1
x
2
⊕
y
2
⊕
y
2
x
1
⊕
y
1
⊕
y
1
x
2
⊕
y
1
x
1
,
which is not a Rothaus function, because it does not contain the monomial y
1
y
2.In [22] we introduced the following construction of bent functions of n
+
2 variables using bent functions of n variables and the minterms of two variables.Theorem 17.
(1) (Corollary 1 of [22]). If f
(
x
) is a bent function of n variables and if i
∈
{
0,1
,
2,3
}, then
(52)
A
f
(
y
,
x
)
=
f
(
x
)
⊕
m
i
(
y
)
is a bent function of n
+
2 variables.
(2) (Corollary 2 of [22]). Let f
0
(
x
) and f
1
(
x
) be bent functions of n variables such that
(53)
f
1
(
x
)
≠
f
0
(
x
)
,
f
1
(
x
)
≠
1
⊕
f
0
(
x
)
.
Ifσ is any permutation of {
0,1
,
2,3
}, then
(54)
B
f
0
,
f
1
(
y
,
x
)
=
(
m
σ
(
0
)
(
y
)
⊕
m
σ
(
1
)
(
y
)
)
f
0
(
x
)
⊕
m
σ
(
2
)
(
y
)
f
1
(
x
)
⊕
m
σ
(
3
)
(
y
)
(
1
⊕
f
1
(
x
)
)
is a bent function of n
+
2 variables.In addition, we also establish [22, Theorem 3] that the number of different bent functions of n
+
2 variables we can construct using the previous theorem is
(55)
6
ν
n
2
-
8
ν
n
,
that is, 4
ν
n from Theorem 17(1) and 6
ν
n
2
-
12
ν
n from Theorem 17(2).According to expression (10) it is evident that Corollary 6 and Theorem 17(1) provide the same bent functions. It is also evident that the bent functions constructed by Corollary 7 can be obtained by Theorem 17(2) if we take
(56)
(
f
0
(
x
)
,
f
1
(
x
)
)
=
(
f
(
x
⊕
u
)
,
f
(
x
)
)
or
(
f
0
(
x
)
,
f
1
(
x
)
)
=
(
f
(
x
⊕
u
)
,
1
⊕
f
(
x
)
)
.
In fact, for n
=
2, both constructions provide the same bent functions of n
+
2
=
4 variables. The following result establishes that this is the only case when both constructions provide the same bent functions.Theorem 18.
Letf
0
(
x
), f
1
(
x
), and f
(
x
) be bent functions of n variables and consider u
∈
ℤ
2
n
∖
{
0
}. If
(57)
(
f
0
(
x
)
,
f
1
(
x
)
)
≠
(
f
(
x
⊕
u
)
,
f
(
x
)
)
,
(
f
0
(
x
)
,
f
1
(
x
)
)
≠
(
f
(
x
⊕
u
)
,
1
⊕
f
(
x
)
)
,
then B
f
0
,
f
1
(
y
,
x
)
≠
G
f
,
u
(
y
,
x
).Proof.
Ifη
0, η
1, ξ, and ξ
u are the truth tables of the functions f
0
(
x
), f
1
(
x
), f
(
x
), and f
(
x
⊕
u
), respectively, then, according to Theorem 17(2) and Corollary 7, the truth tables of the functions B
f
0
,
f
1
(
y
,
x
) and G
f
,
u
(
y
,
x
) have four blocks (not necessarily in that order and not the same order for all):
(58)
B
f
0
,
f
1
:
η
0
η
0
η
1
1
⊕
η
1
G
f
,
u
:
ξ
ξ
u
ξ
u
1
⊕
ξ
.
IfB
f
0
,
f
1
(
y
,
x
)
=
G
f
,
u
(
y
,
x
), then the four blocks of the second row are a permutation of the four blocks of the first row. But if we consider the 4
! cases corresponding to these permutations, we obtain that u
=
0, (
f
0
(
x
)
,
f
1
(
x
)
)
=
(
f
(
x
⊕
u
)
,
f
(
x
)
), (
f
0
(
x
)
,
f
1
(
x
)
)
=
(
f
(
x
⊕
u
)
,
1
⊕
f
(
x
)
), f
(
x
⊕
u
)
=
1
⊕
f
(
x
), or f
(
x
)
=
1
⊕
f
(
x
). So, in all cases, we obtain a contradiction and, therefore, B
f
0
,
f
1
(
y
,
x
)
≠
G
f
,
u
(
y
,
x
).Although, forn
=
2, both constructions provide the same bent functions of n
+
2
=
4 variables, for n
≥
4, Theorems 18 and 14 ensure that Theorem 17(2) provides (see expression (47) and the comment explaining expression (55))
(59)
6
ν
n
(
ν
n
-
2
n
+
1
)
,
bent functions of n
+
2 variables which cannot be obtained by Corollary 7.Now, the following result, whose proof is similar to the previous one, establishes that none of the bent functions obtained by Corollary8 can be obtained by Theorem 17(2) and vice versa.Theorem 19.
Letf
0
(
x
), f
1
(
x
), and f
(
x
) be bent functions of n variables and assume that {
u
,
v
} is a Gauss-Jordan basis of cardinality 2 of ℤ
2
n; then B
f
0
,
f
1
(
y
,
x
)
≠
H
f
,
u
,
v
(
y
,
x
).So, Theorem19 and expressions (48) and (49) ensure that the number of different bent functions of n
+
2 variables constructed by Corollary 8, which cannot be obtained by Theorem 17(2), is
(60)
(
2
n
+
2
(
2
n
-
3
)
+
8
)
ν
n
.Finally, adding expressions (55) and (60), we have the following result which establishes the number of different bent functions we can construct using Theorems 5 and 17.Theorem 20.
Ifν
n is the number of bent functions of n variables, then using Theorems 5 and 17 we can construct
(61)
6
ν
n
2
+
2
n
+
2
(
2
n
-
3
)
ν
n
,
different bent functions of n
+
2 variables.Table1 summarizes the number of bent functions we can construct using Theorems 5 and 17 compared with the number of bent functions of the classes of Rothaus and Maiorana-McFarland and the iterative construction. The number of Rothaus functions for more than 6 variables is unknown. Also, the number of bent functions of more than 10 variables is unknown. Note that for 4 variables the number of bent functions provided by Theorem 5 or by Theorem 17 (see comments after Theorem 18) is the same as the number of bent functions provided by Rothaus construction; nevertheless, both constructions provide different bent functions as we can see in Example 16. Using the iterative construction of Canteaut and Charpin [43], Tokareva [34] obtain the same number of bent functions for 4 variables and more functions for a greater number of variables, but for 8 and 10 variables, she only provides a lower bound on the number of bent functions that can be obtained. Finally, an exhaustive computer search shows that the 512 bent functions of 4 variables obtained by iterative construction and Theorem 17 are the same.Table 1
Number of bent functions constructed with different methods.
Variables
4
6
8
10
Bent
896
5 425 430 528
99
270
589
265
934
370
305
785
861
242
880
≈
2
106
?
Rothaus
512
?
?
?
Maiorana-McFarland
384
10 321 920
1
371
195
958
099
968
000
≈
2
60
2
150
Iterative construction
512
333 961 408
2
87.35
2
262.16
Theorem17
320
4 809 728
176
611
778
441
522
708
480
≈
2
68
2
214
Theorem5
512
752 640
84
766
926
569
472
≈
2
47
2
128
Theorems5 and 17
512
5 562 368
176
611
863
208
449
277
952
≈
2
68
2
214


## 6. Some Remarks

Note that the bent functions obtained by Theorem5 can be obtained from some affine transformations of the bent function
(62)
A
f
(
y
,
x
)
=
f
(
x
)
⊕
m
3
(
y
)
,
obtained in Theorem 17(1).For example, foru
,
v
∈
𝔽
2
n, consider the (
n
+
2
)
×
(
n
+
2
) matrix,
(63)
M
=
[
1
0
v
0
1
u
0
T
0
T
I
n
]
,
where I
n is the n
×
n identity matrix. It is not difficult to see that the bent function
(64)
A
f
(
(
y
,
x
)
M
)
=
f
(
y
1
v
⊕
y
2
u
⊕
x
)
⊕
y
1
y
2
has the same truth table as the bent function
(65)
B
(
y
,
x
)
=
m
0
(
y
)
f
(
x
)
⊕
m
1
(
y
)
f
(
x
⊕
u
)
⊕
m
2
(
y
)
f
(
x
⊕
v
)
⊕
m
3
(
y
)
(
1
⊕
f
(
x
⊕
u
⊕
v
)
)
,
and, therefore, both expressions define the same bent function. Analogously, for the (
n
+
2
)
×
(
n
+
2
) matrix
(66)
N
=
[
1
0
u
⊕
v
0
1
u
0
T
0
T
I
n
]
,
the bent function
(67)
A
f
(
(
y
,
x
)
N
⊕
(
0
2
,
u
)
)
=
f
(
y
1
(
u
⊕
v
)
⊕
(
y
2
⊕
1
)
u
⊕
x
)
⊕
y
1
y
2
has the same truth table as the bent function
(68)
B
(
y
,
x
)
=
m
1
(
y
)
f
(
x
)
⊕
m
0
(
y
)
f
(
x
⊕
u
)
⊕
m
2
(
y
)
f
(
x
⊕
v
)
⊕
m
3
(
y
)
(
1
⊕
f
(
x
⊕
u
⊕
v
)
)
,
and, therefore, both expressions define the same bent function.We use the construction of Theorem5 instead of the affine transformations because of the following.(i)
As we explained in Example2, not all the bent functions that are affine equivalent to a given function are different. This fact makes the computation of the number of functions we can construct a difficult task.
(ii)
The simplicity of the operations with minterms makes the computation of the support of the new bent functions evident.
(iii)
Finally, in Example11, using two different bent functions of n variables and two different pairs of vectors, we have obtained the same bent function of n
+
2 variables faster and in a clearer fashion. However, to achieve the same result using the affine equivalence, we need a greater number of algebraic manipulations and, besides, it is far from evident the choice of the appropriate pair of vectors to prevent the equality of the obtained functions.The following example emphasizes the latter two items.Example 21.
For the functionsf
(
x
) and g
(
x
) of Example 11, using the first and the second affine transformations introduced at the beginning of this section, we have, after some algebraic manipulations, the following functions:
(69)
H
f
,
1
,
2
(
y
,
x
)
=
f
(
y
1
2
⊕
y
2
1
⊕
x
)
⊕
m
3
(
y
)
=
m
0
(
y
1
⊕
x
1
,
y
2
⊕
x
2
)
⊕
y
1
y
2
,
H
g
,
1
,
3
(
y
,
x
)
=
g
(
y
1
(
1
⊕
3
)
⊕
(
y
2
⊕
1
)
1
⊕
x
)
⊕
m
3
(
y
)
=
m
1
(
y
1
⊕
x
1
,
1
⊕
y
2
⊕
x
2
)
⊕
y
1
y
2
.
As we know, both functions are the same, but, in this way, it is our contention that the support of those functions is not obtainable straightforwardly. Nevertheless, from Example11, the support of the above functions is the set {
0
,
5
,
10
,
12
,
13
,
14
}.



---

*Source: 701298-2014-04-17.xml*