# 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].

##### MSC:
 94A60 Cryptography 06E30 Boolean functions