84
R. S. Stankovi´ c et al.
transition to Gibbs coefficients of bent functions determined by the Gibbs dyadic
derivative suggested in [10] and further extended to multiple-valued functions in
[11–13] permits to clearly differentiate the values to be permuted and determine the
related permutation matrices the structure of which is the subject of study in the
present chapter. It turns out that the Gibbs derivative written as a vector of Gibbs
coefficients of a bent function corresponds to a permutation unique to the function
and its complement [14]. On the other hand the truth table of a bent function can be
permuted in a huge number of ways without changing the function given.
The transition to Gibbs coefficients of bent functions determined by the Gibbs
dyadic derivative was suggested in [10] and used to check bentness of Boolean
functions. An important advantage is taken from the property that computing the
Gibbs derivatives can be performed over GPU systems by exploiting both data and
task parallelism [9]. The same transition permits to clearly differentiate the values
to be permuted and determine the related permutation matrices assigned to bent
functions. This property is used in [12] as a mean to define a characterization of
ternary bent functions. In [13], the permutation matrices assigned to binary bent
functions are used to generate quaternary bent functions due to their encoding
by binary values. In the present work, we analyze the structure of permutation
matrices assigned to bent functions by the Gibbs derivative in terms of appropriately
determined submatrices and their positions within the permutation matrix.
4.2 Background Theory
In this section, we present a necessary theoretical background upon which the
further considerations are based.
4.2.1 Bent Functions
A Boolean function f in n variables, defined as a mapping f : {0, 1} n → {0, 1},
where n is even, is bent if its nonlinearity is as large as possible, i.e., 2 n−1 − 2 n/2−1 .
The Hamming weight, i.e., the number of 1 values in the truth-vector of a bent
function is uniquely specified as either 2 n−1 − 2 n/2−1 or 2 n−1 + 2 n/2−1 . Thus, every
bent function takes the same values as any affine function at the number of points
equal to the Hamming weight. The nonlinearity is defined as the minimum number
of points at which a function equals any affine function and, therefore, for bent
functions it is the maximum possible 2 n−1 − 2 n/2−1 . The degree of a bent function
f , defined as the maximum number of variables in a product term in the positive
polarity Reed–Muller expression for f , is n/2.
Example 4.1 Let f be a bent function. If n = 2, its Hamming weight is 1 or 3,
whereas if n = 4, its Hamming weight is 6 or 10.
R. S. Stankovi´ c et al.
transition to Gibbs coefficients of bent functions determined by the Gibbs dyadic
derivative suggested in [10] and further extended to multiple-valued functions in
[11–13] permits to clearly differentiate the values to be permuted and determine the
related permutation matrices the structure of which is the subject of study in the
present chapter. It turns out that the Gibbs derivative written as a vector of Gibbs
coefficients of a bent function corresponds to a permutation unique to the function
and its complement [14]. On the other hand the truth table of a bent function can be
permuted in a huge number of ways without changing the function given.
The transition to Gibbs coefficients of bent functions determined by the Gibbs
dyadic derivative was suggested in [10] and used to check bentness of Boolean
functions. An important advantage is taken from the property that computing the
Gibbs derivatives can be performed over GPU systems by exploiting both data and
task parallelism [9]. The same transition permits to clearly differentiate the values
to be permuted and determine the related permutation matrices assigned to bent
functions. This property is used in [12] as a mean to define a characterization of
ternary bent functions. In [13], the permutation matrices assigned to binary bent
functions are used to generate quaternary bent functions due to their encoding
by binary values. In the present work, we analyze the structure of permutation
matrices assigned to bent functions by the Gibbs derivative in terms of appropriately
determined submatrices and their positions within the permutation matrix.
4.2 Background Theory
In this section, we present a necessary theoretical background upon which the
further considerations are based.
4.2.1 Bent Functions
A Boolean function f in n variables, defined as a mapping f : {0, 1} n → {0, 1},
where n is even, is bent if its nonlinearity is as large as possible, i.e., 2 n−1 − 2 n/2−1 .
The Hamming weight, i.e., the number of 1 values in the truth-vector of a bent
function is uniquely specified as either 2 n−1 − 2 n/2−1 or 2 n−1 + 2 n/2−1 . Thus, every
bent function takes the same values as any affine function at the number of points
equal to the Hamming weight. The nonlinearity is defined as the minimum number
of points at which a function equals any affine function and, therefore, for bent
functions it is the maximum possible 2 n−1 − 2 n/2−1 . The degree of a bent function
f , defined as the maximum number of variables in a product term in the positive
polarity Reed–Muller expression for f , is n/2.
Example 4.1 Let f be a bent function. If n = 2, its Hamming weight is 1 or 3,
whereas if n = 4, its Hamming weight is 6 or 10.