zbMATH — the first resource for mathematics

On cryptographic complexity of Boolean functions. (English) Zbl 1021.94524
Mullen, Gary L. (ed.) et al., Finite fields with applications to coding theory, cryptography and related areas. Proceedings of the 6th international conference on finite fields and applications, Oaxaca, México, May 21-25, 2001. Berlin: Springer. 53-69 (2002).
Summary: Cryptographic Boolean functions must be complex to satisfy Shannon’s principle of confusion. Two main criteria evaluating, from the crytpographic viewpoint, the complexity of Boolean functions on \(F^n_2\) have been studied in the literature: the nonlinearity (the minimum Hamming distance to affine functions) and the algebraic degree. We consider two other criteria: the minimum number of terms in the algebraic normal forms of all affinely equivalent functions (we call it the algebraic thickness) and the non-normality. We show that, asymptotically, almost all Boolean functions have high algebraic degrees, high nonlinearities, high algebraic thicknesses and are highly non-normal.
For the entire collection see [Zbl 0995.00009].

94A60 Cryptography
06E30 Boolean functions