On the algebraic thickness and non-normality of Boolean functions
Claude Carlet · 2004
Cryptographic Boolean functions must be complex to satisfy Shannon's principle of confusion. From the cryptographic viewpoint, the two main criteria in evaluating the complexity of Boolean functions on F/sub 2//sup n/ are the nonlinearity and the algebraic degree. Two other criteria have also been considered: the algebraic thickness and the non-normality. It is known that, asymptotically, almost all Boolean functions have high algebraic thicknesses and are deeply non-normal, and, as well, they have high algebraic degrees and high nonlinearities. We improve upon this result and, recalling a relationship between non-normality and nonlinearity, we prove a new result on symmetric functions, which implies, as a direct consequence, the known results on their nonlinearities (this gives some new insight on the reasons for their behavior).