Construction of Bent Functions by FFT-like Permutation Matrices

In this chapter, we first present a particular class of permutation matrices introduced in [1, 2] as FFT-like permutation matrices, since they are derived from a particular factorization of Discrete Fourier Transform (DFT) matrices leading to the Fast Fourier Transform (FFT) as a fast algorithm to compute the DFT spectra [3]. These permutation matrices can be efficiently used to construct bent functions by modifying given bent functions. This statement follows from the observation that spectral invariant operations, which preserve bentness, perform particular precisely specified permutations of subsets of spectral coefficients. These permutations in the spectral domain can be equivalently expressed as permutations over function values involved in computing the corresponding spectral coefficients. The function values used to compute a spectral coefficient are uniquely determined by the positions from which the data are fetched in steps of FFT algorithms for the Walsh and the Vilenkin-Chrestenson transforms, respectively, for binary- and multiple-valued functions.