Chapter 4
Towards the Structure of a Class
of Permutation Matrices Associated
with Bent Functions
Radomir S. Stankovi´ c, Milena Stankovi´ c, Jaakko T. Astola,
and Claudio Moraga
4.1 Introduction
Bent functions are a special class of Boolean functions with interesting properties, as
high nonlinearity, and due to that, with important applications in few areas including
cryptography as probably the most attractive among them [1, 15]. They are a very
small portion of the total number of Boolean functions for a given number of
variables. From the spectral point of view, all bent functions belong to the single
class of functions with the flat Walsh spectrum. This property implies that spectra
of bent functions are mutually different in the order of Walsh coefficients, with all
the coefficients having the same absolute value equal 2 n/2 , where n is the number
of variables.
The same statement about the mutual difference of bent functions in terms of
permutations is true also in the Boolean domain recalling that bent functions have a
determined number of non-zero values and, therefore, can be split into two subsets
of functions with respect to the number of non-zero values. These subsets are of the
same cardinality and functions in a subset are logic complements of functions in the
other. Permutations that relate two bent functions are hard to observe either in the
Boolean or Walsh spectral domain, since in both cases, there are just two different
values in the vectors of function values and spectral coefficients to be permuted. The
R. S. Stankovi´ c ()
Mathematical Institute of SASA, Belgrade, Serbia
M. Stankovi´ c
Department of Computer Science, Faculty of Electronic Engineering, Niš, Serbia
J. T. Astola
Department of Signal Processing, Tampere University of Technology, Tampere, Finland
C. Moraga
Technical University of Dortmund, Dortmund, Germany
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_4
83
Towards the Structure of a Class
of Permutation Matrices Associated
with Bent Functions
Radomir S. Stankovi´ c, Milena Stankovi´ c, Jaakko T. Astola,
and Claudio Moraga
4.1 Introduction
Bent functions are a special class of Boolean functions with interesting properties, as
high nonlinearity, and due to that, with important applications in few areas including
cryptography as probably the most attractive among them [1, 15]. They are a very
small portion of the total number of Boolean functions for a given number of
variables. From the spectral point of view, all bent functions belong to the single
class of functions with the flat Walsh spectrum. This property implies that spectra
of bent functions are mutually different in the order of Walsh coefficients, with all
the coefficients having the same absolute value equal 2 n/2 , where n is the number
of variables.
The same statement about the mutual difference of bent functions in terms of
permutations is true also in the Boolean domain recalling that bent functions have a
determined number of non-zero values and, therefore, can be split into two subsets
of functions with respect to the number of non-zero values. These subsets are of the
same cardinality and functions in a subset are logic complements of functions in the
other. Permutations that relate two bent functions are hard to observe either in the
Boolean or Walsh spectral domain, since in both cases, there are just two different
values in the vectors of function values and spectral coefficients to be permuted. The
R. S. Stankovi´ c ()
Mathematical Institute of SASA, Belgrade, Serbia
M. Stankovi´ c
Department of Computer Science, Faculty of Electronic Engineering, Niš, Serbia
J. T. Astola
Department of Signal Processing, Tampere University of Technology, Tampere, Finland
C. Moraga
Technical University of Dortmund, Dortmund, Germany
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_4
83