zbMATH — the first resource for mathematics

Construction of nonlinear Boolean functions with important cryptographic properties. (English) Zbl 1082.94529
Preneel, Bart (ed.), Advances in cryptology - EUROCRYPT 2000. 19th international conference on the theory and application of cryptographic techniques, Bruges, Belgium, May 14–18, 2000. Proceedings. Berlin: Springer (ISBN 3-540-67517-5). Lect. Notes Comput. Sci. 1807, 485-506 (2000).
This paper addresses the problem of obtaining new construction methods for cryptographically significant Boolean functions. We show that for each positive integer \(m\), there are infinitely many integers \(n\) (both odd and even), such that it is possible to construct \(n\)-variable, \(m\)-resilient functions having nonlinearity greater than \(2^{n-1}-2^{[\frac n2]}\). Also we obtain better results than all published works on the construction of \(n\)-variable, \(m\)-resilient functions, including cases where the constructed functions have the maximum possible algebraic degree \(n-m-1\). Next we modify the Patterson-Wiedemann functions to construct balanced Boolean functions on \(n\)-variables having nonlinearity strictly greater than \(2^{n-1}-2^{\frac{n-1}2}\) for all odd \(n\geq 15\). In addition, we consider the properties strict avalanche criteria and propagation characteristics which are important for design of \(S\)-boxes in block ciphers and construct such functions with very high nonlinearity and algebraic degree.
For the entire collection see [Zbl 0939.00052].

94A60 Cryptography
06E30 Boolean functions