4 Permutation Matrices Associated to Bent Functions
97
Recall that the Gibbs coefficients for a function f and its logic complement f differ
just in the sign but have identical absolute values.
Remark 4.1 When a given Gibbs permutation matrix is applied to all bent functions,
all these functions are again obtained. It follows that each Gibbs permutation matrix
converts a bent function into a bent function of the same number of variables.
When all Gibbs permutation matrices are applied to the same bent function, a
subset of bent functions is obtained. This observation will be discussed in more
detail in the following example.
Consider the basic bent function for n = 4 and two functions derived from it by
permuting the variables
f b 1 = x 1 x 2 ⊕ x 3 x 4 ,
f b 2 = x 1 x 3 ⊕ x 2 x 4 ,
f b 3 = x 1 x 4 ⊕ x 2 x 3 .
When all 448 Gibbs permutation matrices are applied to f b 1 , we obtain
1. 192 other mutually different bent functions.
2. Additional 16 functions are obtained 16 times each. This means that 16 different
Gibbs permutation matrices produce a specific bent function f s 1 when applied to
f b 1 . Another 16 Gibbs permutation matrices produce another specific function
f s 2 . There are 16 specific functions produced by 16 different subsets of Gibbs
permutation matrices.
3. 240 bent functions are not generated from f b 1 by the application of all 448 Gibbs
permutation matrices.
The term specific functions is used with no other reason or justification but
to differentiate these 16 functions that cannot be obtained from the three basic
bent functions from other bent functions obtained by the application of the Gibbs
permutation matrices to them.
The same results are obtained when the permutation matrices are applied to
other two basic functions derived by permuting variables in f b 1 . For the three
basic functions, the sets of 192 functions obtained by the application of all Gibbs
permutation matrices as well as sets of 16 functions obtained 16 times are different
but not disjoint. The same is true when all Gibbs permutation matrices are applied
to any bent function not just the basic functions.
When all permutation matrices are applied to two basic bent functions, for
example, f b 1 = x 1 x 2 ⊕x 3 x 4 and f b 2 = x 1 x 3 ⊕x 2 x 4 , then 256 functions are generated
a single time, 64 are generated 2 times, 32 are generated 16 times, and 96 functions
are not generated. The same results are obtained for any combination of two basic
functions.
When we apply all 448 permutation matrices to the three basic bent functions,
all bent functions except 16 are produced. These 16 functions that cannot be
97
Recall that the Gibbs coefficients for a function f and its logic complement f differ
just in the sign but have identical absolute values.
Remark 4.1 When a given Gibbs permutation matrix is applied to all bent functions,
all these functions are again obtained. It follows that each Gibbs permutation matrix
converts a bent function into a bent function of the same number of variables.
When all Gibbs permutation matrices are applied to the same bent function, a
subset of bent functions is obtained. This observation will be discussed in more
detail in the following example.
Consider the basic bent function for n = 4 and two functions derived from it by
permuting the variables
f b 1 = x 1 x 2 ⊕ x 3 x 4 ,
f b 2 = x 1 x 3 ⊕ x 2 x 4 ,
f b 3 = x 1 x 4 ⊕ x 2 x 3 .
When all 448 Gibbs permutation matrices are applied to f b 1 , we obtain
1. 192 other mutually different bent functions.
2. Additional 16 functions are obtained 16 times each. This means that 16 different
Gibbs permutation matrices produce a specific bent function f s 1 when applied to
f b 1 . Another 16 Gibbs permutation matrices produce another specific function
f s 2 . There are 16 specific functions produced by 16 different subsets of Gibbs
permutation matrices.
3. 240 bent functions are not generated from f b 1 by the application of all 448 Gibbs
permutation matrices.
The term specific functions is used with no other reason or justification but
to differentiate these 16 functions that cannot be obtained from the three basic
bent functions from other bent functions obtained by the application of the Gibbs
permutation matrices to them.
The same results are obtained when the permutation matrices are applied to
other two basic functions derived by permuting variables in f b 1 . For the three
basic functions, the sets of 192 functions obtained by the application of all Gibbs
permutation matrices as well as sets of 16 functions obtained 16 times are different
but not disjoint. The same is true when all Gibbs permutation matrices are applied
to any bent function not just the basic functions.
When all permutation matrices are applied to two basic bent functions, for
example, f b 1 = x 1 x 2 ⊕x 3 x 4 and f b 2 = x 1 x 3 ⊕x 2 x 4 , then 256 functions are generated
a single time, 64 are generated 2 times, 32 are generated 16 times, and 96 functions
are not generated. The same results are obtained for any combination of two basic
functions.
When we apply all 448 permutation matrices to the three basic bent functions,
all bent functions except 16 are produced. These 16 functions that cannot be